Migrated from Lutece 3205 线性代数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 容斥，dp

对于非空非负数集 $S$，称数集 $T$ 是 $S$ 的一组基当且仅当对于 $S$ 中的每个数 $s$，存在 $T$ 的一个子集满足这个子集的异或和等于 $s$。

同时定义 $T$ 是 $S$ 的一个最小基当且仅当 $T$ 是 $S$ 的基中元素个数最少的。

现在给定数集 $B$ 和一个正整数 $N$，求有多少 $\{1,2,...,N\}$ 的子集 $X$ 满足 $B$ 是 $X$ 的一个最小基，对 $998244353$ 取模。

Input

$B$ 和 $N$ 以二进制形式给出，高位在前，可能有前导零。

第一行两个整数 $n,m$，分别表示数集 $B$ 的大小和二进制数的位数。

接下来 $n$ 行，每行一个长为 $m$ 的 $01$ 串表示 $B$ 中的数。

最后一行一个长为 $m$ 的 $01$ 串表示 $N$。

Output

一行一个整数表示答案。

Samples

4 4
0001
0010
0100
1000
1101

7364

3 2
00
00
00
11

0

3 10
1111100110
0011110100
0101100001
1110000001

38

Constraints

$1\le n,m\le 2000$

Resources

2024 UESTC ICPC Training for Math