题目描述

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

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

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

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

输入格式

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

$N$ $X$ $A_1$ $:$ $A_N$

输出格式

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

题目大意

有$N$个数$A_{i...N}$写在黑板上，现在有两种可以执行无限次的操作：

当$X$在黑板上时把$2X$也写在黑板上

当$X$和$Y$都在黑板上时，把$XxorY$写在黑板上

求最终有多少个$≤M$的数能被写在黑板上。

$1≤N≤6$, $0≤A_{i...N}≤2^{4000}$

感谢@psk011102 提供的翻译

3 111
1111
10111
10010

4

4 100100
1011
1110
110101
1010110

37

4 111001100101001
10111110
1001000110
100000101
11110000011

1843

1 111111111111111111111111111111111111111111111111111111111111111
1

466025955

提示

制約

• $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$ である

Sample Explanation 1

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

Sample Explanation 4

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