分数: 1000 点
问题陈述
有 N 写在黑板上的非负整数。的 i- 第一个整数是 A_i.
Takahashi 可以以任意顺序执行任意次数的以下两种操作:
- 选择黑板上写的一个整数(令该整数为 X)。写 板上的 2X ,不擦除所选的整数。
- 选择写在黑板上的两个整数,可能相同(让这些整数为 X 和 Y)。写 板上的 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 写 30.
- 进行异或 30 和 18 写 12.
- 双 12 写 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.