题目描述

有 $N$ 个非负整数写在黑板上，第 $i$ 个整数是 $A_i$。

Takahashi 可以任意次数、任意顺序地执行以下两种操作：

• 选择一个写在黑板上的整数（记为 $X$）。将 $2X$ 写在黑板上，不擦除已选中的整数。
• 选择两个写在黑板上的整数，可以相同（记为 $X$ 和 $Y$）。将它们的按位异或（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$）用二进制表示法给出，并且它们的最高有效位均为 $1$。

输入

输入以以下格式从标准输入给出：

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

输出

打印不超过 $X$ 的不同整数可以被写在黑板上的数量。

示例输入1

3 111
1111
10111
10010

示例输出1

4

最初，黑板上写着 $15$，$23$ 和 $18$。在不超过 $7$ 的整数中，可以写下四个整数：$0$，$3$，$5$ 和 $6$。例如，可以以下列方式写下 $6$：

• 将 $15$ 乘以 $2$，写下 $30$。
• 将 $30$ 与 $18$ 进行按位异或，写下 $12$。
• 将 $12$ 乘以 $2$，写下 $24$。
• 将 $30$ 与 $24$ 进行按位异或，写下 $6$。

示例输入2

4 100100
1011
1110
110101
1010110

示例输出2

37

示例输入3

4 111001100101001
10111110
1001000110
100000101
11110000011

示例输出3

1843

示例输入4

1 111111111111111111111111111111111111111111111111111111111111111
1

示例输出4

466025955

请确保对结果取模 $998244353$。