题目描述

给你一个集合 $B$ 和一个整数 $X$，你要求出有多少个非空集合 $S\subseteq \{1,2,3,\dots,X\}$，使得 $B$ 是 $S$ 的线性基。答案对 $998244353$ 取模。

称一个集合 $B$ 是另一个集合 $S$ 的线性基，当且仅当 $S$ 中任意元素都能被表示为 $B$ 中若干元素的异或和，且 $B$ 是所有这样的集合中大小最小的（可能有多个最小的）。

输入格式

第一行两个整数 $n,m$，$n$ 为集合 $B$ 的大小，$B$ 中所有元素以及 $X$ 均不超过 $2^m-1$。不保证 $B$ 中没有重复元素。

接下来 $n$ 行，每行一个长为 $m$ 的 01 字符串，第 $i$ 行为 $B_i$ 的二进制表示，行末为最低位。

最后一行一个长为 $m$ 的 01 字符串，为 $X$ 的二进制表示。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

输入样例1

2 2
01
10
11

输出样例1

4

样例 $1$ 解释：

$B_1=1$，$B_2=2$，$X=3$，集合 $\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$ 是合法的。

输出样例2

3 3
001
010
101
110

输出样例2

38

数据范围

对于所有数据，$1\le n,m\le 2000$。

特殊性质 A：保证 $n=m$，$X=2^m-1$