Ralph And His Magic Field

Ralph에게는 n × m개의 블록으로 나뉜 마법의 들판이 있다. 즉, 들판에는 n개의 행과 m개의 열이 있다. Ralph는 각 블록에 정수를 하나씩 넣을 수 있다. 하지만 마법의 들판이 항상 제대로 작동하는 것은 아니다. 각 행과 각 열에 있는 정수의 곱이 k와 같을 때만 제대로 작동하며, k는 1 또는 -1이다.

Now Ralph는 마법의 들판이 제대로 작동하도록 각 블록에 수를 넣는 방법의 수를 구해 달라고 한다. 적어도 하나의 블록에서 첫 번째 방법의 수와 두 번째 방법의 수가 다를 때, 그리고 그럴 때에만 두 방법을 서로 다르다고 간주한다. 답을 1000000007 = 109 + 7로 나눈 나머지를 출력해야 한다.

블록에 넣을 수의 범위에는 제한이 없지만, 답이 무한대가 아님을 증명할 수 있음에 유의하라.

유일한 줄에 세 정수 n, m, k (1 ≤ n, m ≤ 1018, k is either 1 or -1)가 주어진다.

답을 1000000007로 나눈 나머지를 나타내는 수 하나를 출력한다.

첫 번째 예제에서는 유일한 블록에 -1을 넣는 방법만 가능하다.

두 번째 예제에서는 모든 블록에 1을 넣는 방법만 가능하다.