← 返回题目列表

AtCoder · code_thanks_festival_2017_f

F. 有限异或子集

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

配点 : 500 点

問題文

N 正整数, 第i(1≦i≦N) 个正整数是 共 a_i 。
N 个整数 选择 0 或更多,并计算所有选定整数的按位异或。
计算结果为 找出选择整数的方法的数量,使得 K 除以 10^9+7 求余数。 当选择
但是,0 时,按位异或为 0 。

制約

  • 1≦N≦10^5
  • 0≦K≦10^5
  • 1≦a_i (1≦i≦N)
  • a_1 + … + a_N≦10^5
  • 所有输入均为整数。

入力

输入将以以下格式从标准输入给出。

N K 
a_1
: 
a_N

出力

选择满足条件的整数的方法数为 打印除以 10^9+7 后的余数。


入力例 1

4 3
1
2
1
2

出力例 1

4

所有选定整数的按位异或为 以下是如何选择以便 K = 3 以下是如何选择 4 没错。

  • \{a_1,a_2\}
  • \{a_1,a_4\}
  • \{a_2,a_3\}
  • \{a_3,a_4\}

入力例 2

4 0
1
1
1
1

出力例 2

8

所有选定整数的按位异或为 以下是如何选择以便 K = 0 以下是如何选择 8 没错。

  • \{\} (所选整数为 0 )
  • \{a_1,a_2\}
  • \{a_1,a_3\}
  • \{a_1,a_4\}
  • \{a_2,a_3\}
  • \{a_2,a_4\}
  • \{a_3,a_4\}
  • \{a_1,a_2,a_3,a_4\}

入力例 3

13 3
2
7
1
8
2
8
1
8
2
8
4
5
9

出力例 3

512