問題文

すぬけ君は黒板に 2 つの異なる整数 X,Y と K 行 K 列のマス目を書きました。 次に、すぬけ君はマス目の i 行 j 列目に整数 A_{i,j} を書きました。

すぬけ君はこれを使って、長さ K の数列 a が以下の条件を満たすとき a を 良い数列 と呼ぶことにしました。

• 条件：1 \leq i,j \leq K を満たすどの (i,j) についても、以下が成立する
  • a_i xor a_j xor X あるいは a_i xor a_j xor Y が A_{i,j} と一致する。
  • ただし、xor はビットごとの排他的論理和を表す。

すぬけ君は N 個の整数を持っています。i 番目の整数は x_i です。 すぬけ君はこれら N 個の数から K 個を選んで並べて、長さ K の数列を作ることにしました。 すぬけ君が作ることのできる数列のうち、良い数列であるようなものはいくつありますか？ modulo 10^{9} + 7 で求めてください。

ある数列の作り方は複数あるかもしれませんが、最終的に得られる数列として同じであれば区別しないことに注意してください。 詳しくはサンプル 1 も参照してください。

制約

• 1 \leq N \leq 2048
• 1 \leq K \leq {\rm min}(1024,N)
• 0 \leq X,Y,x_i, A_{i,j} < 2048
• X \neq Y
• 与えられる入力は全て整数

入力例 1

6 3 1 0
0 8 1 2 15 8
1 2 8
2 0 10
8 10 1

出力例 1

2

• 答えとしてありうる数列は (0,2,8) と (1,2,8) の 2 通りです。
• (0,2,8) となるように数を選んで並べる方法は 2 通りありますが、それらは区別しないことに注意してください。

入力例 2

2 2 0 4
0 1
8 16
110 12

出力例 2

0

• どのような数列であっても条件を満たすことはありません。

入力例 3

35 4 11 1
23 2 17 16 22 22 6 0 0 15 16 5 12 21 0 9 17 0 2 26 22 19 6 16 13 7 26 8 22 29 26 13 8 32 14
1 0 15 31
0 11 14 20
5 4 1 17
21 20 27 1

出力例 3

26