配点 : $1000$ 点

問題文

黒板に、$N$ 個の非負整数が書かれています。$i$ 個目の非負整数は、$A_i$ です。

高橋君は、以下の $2$ 種類の操作を、好きな順番で何回でも行うことができます。

• 黒板に書かれている整数を $1$ つ選び、その整数の $2$ 倍の整数を新たに書き加える。選ばれた整数も、そのまま残しておく。
• 黒板に書かれている相異なるとは限らない整数を $2$ つ選び、その $2$ 整数の bitwise xor を新たに書き加える。選ばれた整数も、そのまま残しておく。

黒板に書かれうる整数のうち、$X$ 以下のものは何種類あるでしょうか。なお、最初に黒板に書かれていた整数も、黒板に書かれうる整数とみなします。 答えは非常に大きくなる可能性があるので、$998244353$ で割った余りを求めてください。

制約

• $1 \leq N \leq 6$
• $1 \leq X < 2^{4000}$
• $1 \leq A_i < 2^{4000}(1\leq i\leq N)$
• 入力は全て整数である
• $X,A_i(1\leq i\leq N)$ は $2$ 進表記で与えられ、先頭の桁は $1$ である

入力

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

$N$ $X$

$A_1$

$:$

$A_N$

出力

黒板に書かれうる整数のうち、$X$ 以下のものの個数を $998244353$ で割った余りを出力せよ。

3 111
1111
10111
10010

4

最初、黒板には $15,23,18$ が書かれています。$7$ 以下の整数のうち、$0,3,5,6$ の $4$ 数を書くことができます。 例えば、$6$ は以下のような操作によって書くことができます。

• $15$ を $2$ 倍し、$30$ を書く
• $30$ と $18$ の xor をとり、$12$ を書く
• $12$ を $2$ 倍し、$24$ を書く
• $30$ と $24$ の xor をとり、$6$ を書く

4 100100
1011
1110
110101
1010110

37

4 111001100101001
10111110
1001000110
100000101
11110000011

1843

1 111111111111111111111111111111111111111111111111111111111111111
1

466025955

$998244353$ で割った余りを求めてください。