题目描述

给定整数 $N,M,X$，以及 $K$ 个正整数 $b_1,b_2,\cdots,b_K$，求有多少长为 $M$ 的整数序列 $a_1,a_2,\cdots,a_M$，满足：

• $0\le a_i<2^N$。
• 存在一个子序列 $a_{i_1},a_{i_2},\cdots,a_{i_k}$（$1\le i_1<i_2<\cdots<i_k\le M$），使得 $a_{i_1}\oplus a_{i_2}\oplus\cdots\oplus a_{i_k}\ge X$。
• 对于每个 $j=1,\cdots,K$，存在一个子序列 $a_{i_1},a_{i_2},\cdots,a_{i_k}$（$1\le i_1<i_2<\cdots<i_k\le M$），使得 $a_{i_1}\oplus a_{i_2}\oplus\cdots\oplus a_{i_k}=b_j$。

其中 $\oplus$ 表示异或。答案对 $10^9+7$ 取模。

输入格式

第一行：三个整数 $N,M,K$。

第二行：一个长为 $N$ 的 01 串，为 $X$ 从高位到低位的二进制表示。

接下来 $K$ 行：第 $i$ 行一个长为 $N$ 的 01 串，为 $b_i$ 从高位到低位的二进制表示。

输出格式

一个整数，表示答案。

样例输入1

4 4 1
0101
0010

样例输出1

39060

样例输入2

8 10 3
00000000
01101101
11001001
11101111

样例输出2

3836934

样例输入 3

8 10 0
10010110

样例输出 3

808800473

样例输入4

8 20 8
11101010
01010100
00110110
11100011
11100100
11100011
01010101
10110000
00000111

样例输出4

443121994

数据范围

对于所有数据，满足 $1\le N\le 5000$，$1\le M\le 10^9$，$0\le K\le 1000$，$0\le X<2^N$，$1\le b_i<2^N$。