Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
整数 n, m, k が入力として与えられます。このとき、以下の条件を満たす長さ n の数列 s の個数を 10^9 + 7 で割った余りを求めてください。
- s_i (1 \leq i \leq n) は 0 以上 m 以下の整数である。
- 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.
- s_i (1 \leq i \leq n) is an integer greather than or equal to 0, and less than or equal to m.
- 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