← 返回题目列表

AtCoder · kupc2017_k

K. 异或求和模式

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

你有 3 整数 n, m,和 k。计算长度的数字序列的数量 n,满足以下条件,模 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

输出

打印满足上述条件的数字序列的数量,模 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