配点 : 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