K - Xor Summation Pattern 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 400 点

問題文

整数 n, m, k が入力として与えられます。このとき、以下の条件を満たす長さ n の数列 s の個数を 10^9 + 7 で割った余りを求めてください。

  1. s_i (1 \leq i \leq n) は 0 以上 m 以下の整数である。
  2. 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n = k である。ただし、xor はビットごとの排他的論理和を表すものとする。

制約

  • n, m, k は整数である。
  • 0 \leq n, m, k \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

n m k

出力

問題文の条件を満たす数列 s の個数を 10^9 + 7 で割った余りを出力せよ。

入力例1

0 0 0

出力例1

1

長さが 0 の数列は 1 通りです。このときこの数列は条件 2 も満たします。

入力例2

1 1 0

出力例2

1

入力例3

3 2 3

出力例3

6

以下の 6 通りの数列が存在します。

  • { 0, 1, 2 }
  • { 0, 2, 1 }
  • { 1, 0, 2 }
  • { 1, 2, 0 }
  • { 2, 0, 1 }
  • { 2, 1, 0 }

入力例4

10 10 15

出力例4

620478679

Score : 400 points

Problem Statement

You have 3 integers n, m, and k. Count the number of numerical sequences of length n, which satisfy the following conditions, modulo 10^9 + 7.

  1. s_i (1 \leq i \leq n) is an integer greather than or equal to 0, and less than or equal to m.
  2. 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n = k. xor represents bitwise exclusive OR.

Constraints

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

Input

Input is given from Standard Input in the following format:

n m k

Output

Print the number of numerical sequences that satisfy the above conditions, modulo 10^9 + 7.

Sample Input 1

0 0 0

Sample Output 1

1

The number of numerical sequences with length 1 is 1. This sequence satisfies condition 2.

Sample Input 2

1 1 0

Sample Output 2

1

Sample Input 3

3 2 3

Sample Output 3

6

The following 6 sequences satisfy the constraints.

  • { 0, 1, 2 }
  • { 0, 2, 1 }
  • { 1, 0, 2 }
  • { 1, 2, 0 }
  • { 2, 0, 1 }
  • { 2, 1, 0 }

Sample Input 4

10 10 15

Sample Output 4

620478679

出典

KUPC2017