分数: 400 点
问题陈述
你有 3 整数 n, m,和 k。计算长度的数字序列的数量 n,满足以下条件,模 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
输出
打印满足上述条件的数字序列的数量,模 10^9 + 7.
示例输入 1
0 0 0
示例输出 1
1
具有长度的数值序列的数量 1 is 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