問題文

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
• 入力は全て整数である。

入力例 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