题目描述

サンプルケース3に不備があったので、リジャッジをしました。申し訳ございません。(21:01)

square1001は, Atcoder社から長さ $n$ の数列 $a$ をもらいました。$a$ の要素はすべて異なります。
彼は, 数列 $b$ を作りましたが, この数列を覚えていません。しかし, 次のことは覚えています。 - $b$ の要素はすべて異なる。

• $b$ の要素はすべて $a$ にも入っている。
• square'1001' は, 2進数が好きなため, $ b_1\ \oplus\ b_2\ \oplus\ \cdots\ \oplus\ b_r\ =\ k $ ($r$ は数列 $b$ の長さ) であることも覚えている。[$\oplus$ は XOR]

square1001は, 数列 $b$ として考えられるものが何通りあるのか考えることにしました。
しかし, 彼は全探索をしようとしていて, これに気付いたあなたは, 彼の代わりに求めてあげようとしました。
そのとき, square'1001'が作った数列 $b$ として考えられるものは, 何通りあるでしょうか?
ただし, 答えが非常に大きくなることがあるので, $1,000,000,007$で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$n\ k$ $a_1\ a_2\ \cdots\ a_n$

• $1$ 行目には、数列$a$の長さ$n$と、数列$b$のXORした値$k$が空白区切りで与えられる。
• $2$ 行目には、数列$a$の要素が空白区切りで与えられる。

输出格式

出力は以下の形式で標準出力に従うこと。

• square'1001'が作った数列として考えられるものの通り数を1行に出力せよ。
• ただし, $1,000,000,007$ で割った余りを出力すること。

题目大意

$n$个数选若干个，异或起来是$k$，有多少种选法？

答案可能过大，对$10^9+7$取模。

$1 \le n \le 100$

$1 \le a_i, k \le 255$

$i \neq j \Rightarrow a_i \neq a_j$

注意，$\{2,3\}$与$\{3,2\}$是不同的选法。

3 1
1 2 3

3

3 10
8 7 5

6

25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125

235924722

提示

制約

• $1\ \le\ n\ \le\ 100$
• $1\ \le\ a_i,\ k\ \le\ 255$
• $i\ \neq\ j\ \Rightarrow\ a_i\ \neq\ a_j$

小課題

小課題1 [ $50$ 点 ]

• $1\ \le\ n\ \le\ 4$ を満たす。

小課題2 [ $170$ 点 ]

• $1\ \le\ n\ \le\ 20$ を満たす。

小課題3 [ $180$ 点 ]

• $1\ \le\ n\ \le\ 100$ を満たす。

Sample Explanation 1

数列 $b$ として考えられるのは, $b\ =\ \{\ 1\ \},\ \{\ 2,\ 3\ \},\ \{\ 3,\ 2\ \}$ の3つである。

Sample Explanation 2

数列 $b$ として考えられるのは, $ b\ =\ \{\ 5,\ 7,\ 8\ \},\ \{\ 5,\ 8,\ 7\ \},\ \{\ 7,\ 5,\ 8\ \},\ \{\ 7,\ 8,\ 5\ \},\ \{\ 8,\ 5,\ 7\ \},\ \{\ 8,\ 7,\ 5\ \} $ の6つである。

Sample Explanation 3

$1,000,000,007$ で割った余りを求めること。