Problem Description

Given integers $ n $, $ m $, and $ k $, find the number of sequences $ s $ of length $ n $ that satisfy the following conditions, modulo $ 10^9 + 7 $.

1. $ s_i $ $(1 \leq i \leq n)$ is an integer between $ 0 $ and $ m $ inclusive.
2. $0 \ xor \ s_1 \ xor \ s_2 \ xor \ ... \ xor \ s_n = k$. Here, $ xor $ denotes the bitwise exclusive OR.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ k $

Output Format

Output the number of sequences $ s $ that satisfy the conditions, modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

0 0 0

Sample Output #1

1

Sample Input #2

1 1 0

Sample Output #2

1

Sample Input #3

3 2 3

Sample Output #3

6

Sample Input #4

10 10 15

Sample Output #4

620478679

Notes/Hints

Constraints

• $ n $, $ m $, and $ k $ are integers.
• $0 \leq n, m, k \leq 10^{18}$

Sample Explanation 1

There is only one sequence of length $ 0 $. This sequence also satisfies condition 2.

Sample Explanation 3

The following 6 sequences exist:
- { $ 0 $, $ 1 $, $ 2 $ }
- { $ 0 $, $ 2 $, $ 1 $ }
- { $ 1 $, $ 0 $, $ 2 $ }
- { $ 1 $, $ 2 $, $ 0 $ }
- { $ 2 $, $ 0 $, $ 1 $ }
- { $ 2 $, $ 1 $, $ 0 $ }

见题面 Input 部分

见题面 Output 部分