2021년 최고의 문제

올해는 2021년이다. 사람들은 여전히 COVID에 관심이 많고, NNSU는 ICPC 2020에서 막 우승했으며, 이미 제정신이 아니다. 얼마나 그런지는 아직 모른다. 우리는 SnackDown 결승에 낼 문제를 찾고 있었고, 7dan이 이 문제를 제안했다. 어떤 이유에서인지 그때는 이 문제를 쓰지 않기로 했지만, 내부에서는 The Best Problem of 2021이라는 이름으로 알려지게 되었다.

정수 배열 $B$와 정수 $X$가 주어진다. 원소를 $\mathbf{Z}_2$ 위의 벡터로 보고, 덧셈을 비트 XOR로 할 때, 집합 $\{1, 2, \ldots, X\}$의 부분집합 $S$ 중에서 $B$가 그 기저인 것의 개수를 구하라. 답은 모듈러 998244353으로 나눈 나머지로 출력한다(당연히).

$B$가 $S$의 기저라는 것은, $S$의 모든 원소가 $B$의 원소들의 XOR로 표현되고, 그러한 배열 중 크기가 가장 작다는 뜻이다.

첫 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 2000$)이 주어진다. 각각 $B$의 크기와 이진수 표현의 길이이다. $B$의 모든 원소와 정수 $X$는 정확히 $m$자리 이진수 문자열로 주어지며, 앞자리 0이 있을 수 있다.

다음 $n$개의 줄에는 $B$의 원소를 나타내는 길이 $m$의 이진수 문자열이 한 줄에 하나씩 주어진다.

마지막 줄에는 $X$를 나타내는 길이 $m$의 이진수 문자열이 주어진다.

답은 직접 알아내 보라.