F - Limited Xor Subset Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

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