[Bulgarian2023夏季赛]xor
题目描述
谁不喜欢 xor 呢？🙂
给定整数 n, b, k, u1, …, un，其中：
0 ≤ k, u1, …, un < 2^b
求满足以下两个条件的整数序列 (x1, x2, …, xn) 的数量：
0 ≤ xi ≤ uix1 ^ x2 ^ … ^ xn = k
其中 ^ 表示按位异或（xor）运算。
输入格式
第一行输入两个整数 n 和 b。
第二行输入整数 k，以一个长度为 b 的二进制串形式给出，按从高位到低位的顺序书写。
接下来有 n 行，第 i 行输入整数 ui，同样以长度为 b 的二进制串形式给出，按从高位到低位的顺序书写。
输出格式
输出一行一个整数，表示答案对 998244354 取模后的结果。
限制
1 ≤ n, b, (n + 1) * b ≤ 10 000 000
子任务
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 5 | n, b ≤ 5 |
| 2 | n ≤ 256, b ≤ 8 |
|
| 3 | 15 | n ≤ 8, b ≤ 60 |
| 4 | 10 | n ≤ 11, b ≤ 60 |
| 5 | n ≤ 15, b ≤ 60 |
|
| 6 | 15 | n ≤ 20, b ≤ 60 |
| 7 | 20 | n, b ≤ 3000 |
| 8 | 无额外限制 |
对于某个子任务，只有当该子任务下的所有测试点都通过时，才能获得该子任务的分数。
样例
输入
2 3
000
111
100
输出
5