[ARC084F] XorShift

有$N$个数$A_{i...N}$写在黑板上，现在有两种可以执行无限次的操作： 当$X$在黑板上时把$2X$也写在黑板上 当$X$和$Y$都在黑板上时，把$XxorY$写在黑板上 求最终有多少个$≤M$的数能被写在黑板上。 $1≤N≤6$, $0≤A_{i...N}≤2^{4000}$ 感谢@psk011102 提供的翻译

[problemUrl]: https://atcoder.jp/contests/arc084/tasks/arc084_d 黒板に、$ N $ 個の非負整数が書かれています。$ i $ 個目の非負整数は、$ A_i $ です。 高橋君は、以下の $ 2 $ 種類の操作を、好きな順番で何回でも行うことができます。 - 黒板に書かれている整数を $ 1 $ つ選び、その整数の $ 2 $ 倍の整数を新たに書き加える。選ばれた整数も、そのまま残しておく。 - 黒板に書かれている相異なるとは限らない整数を $ 2 $ つ選び、その $ 2 $ 整数の bitwise xor を新たに書き加える。選ばれた整数も、そのまま残しておく。 黒板に書かれうる整数のうち、$ X $ 以下のものは何種類あるでしょうか。なお、最初に黒板に書かれていた整数も、黒板に書かれうる整数とみなします。 答えは非常に大きくなる可能性があるので、$ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ A_1 $ $ : $ $ A_N $

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

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 $ で割った余りを求めてください。