← 返回题目列表

AtCoder · arc084_d

F. 异或移位

中文机器翻译题面 查看原题

分数: 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.