某大学每年都会有一次Mystery Hunt的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。
作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为Infinite Corridor。一次，你经过这条走廊的时候，注意到在走廊的墙壁上隐藏着$n$个等长的二进制的数字，长度均为$m$。你从西向东将这些数字记录了下来，形成一个含有$n$个数的二进制数组$a_1, a_2 \cdots, a_n$。
很快，在最新的一期Voo Doo杂志上，你发现了$q$个长度也为$m$的二进制串$r_1, r_2, \cdots, r_q$。
聪明的你很快发现了这些数字的含义。
保持数组$a_1, a_2 \cdots, a_n$的元素顺序不变，你可以在它们之间插入$\land$（按位与运算）或者$\vee$（按位或运算）两种二进制运算符。例如：$11011 \land 00111 = 00011，11011 \vee 00111 = 11111$。
你需要插入恰好$n$个运算符，相邻两个数之间恰好一个，在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个0，这就形成了一个运算式，我们可以计算它的值。与往常一样，运算顺序是从左往右。有趣的是，出题人已经告诉你这个值的可能的集合——Voo Doo杂志里的那一些二进制数$r_1, r_2, \cdots, r_q$，而解谜的方法，就是对$r_1, r_2, \cdots, r_q$中的每一个值$r_i$，分别计算出有多少种方法填入这$\mathbf{n}$个运算符，使得这个运算式的值是$r_i$。
然而，Infinite Corridor真的很长，这意味着数据范围可能非常大。因此，答案也可能非常大，但是你发现由于谜题的特殊性，你只需要求答案模$1000000007(10 ^ 9 + 7$, 一个质数)的值。
输入格式
第一行三个数$n,m,q$，含义如题所述。
接下来$n$行，其中第$i$行有一个长度为$m$的二进制串，左边是最高位，表示$a_i$。
接下来$q$行，其中第$i$行有一个长度为$m$的二进制串，左边是最高位，表示$r_i$。
输出格式
输出$q$行，每行一个数，其中第$i$行表示对应于$r_i$的答案。
样例一
input
5 5 1 01110 11011 10000 01010 00100 00100
output
6
explanation
有以下且仅有以下六个运算式的值是$00100_{2}$：(下标2表示被标识的数是二进制数)
$ 0 \land \ 01110_{2} \land \ 11011_{2} \vee {\ 10000}_{2}{\ \land 01010}_{2}{\ \vee 00100}_{2} $
$ 0 \vee \ 01110_{2}\ {\vee 11011}_{2}\ \land {\ 10000}_{2}{\ \ \land 01010}_{2}{\ \vee 00100}_{2} $
$ 0 \land \ 01110_{2}\ {\vee 11011}_{2} \land {\ 10000}_{2}{\ \land 01010}_{2}{\ \vee 00100}_{2} $
$ 0 \vee \ 01110_{2} \land \ 11011_{2} \land {\ 10000}_{2}{\land \ 01010}_{2}{\ \vee 00100}_{2} $
$ 0 \land \ 01110_{2}\ {\land 11011}_{2} \land {\ 10000}_{2}{\ \land 01010}_{2}{\ \vee 00100}_{2} $
$ 0 \vee \ 01110_{2}\ \vee 11011_{2} \vee {\ 10000}_{2}{\ \ \vee 01010}_{2}{\ \land 00100}_{2} $
样例二
input
10 10 3 0100011011 0110100101 1100010100 0111000110 1100011110 0001110100 0001101110 0110100001 1110001010 0010011101 0110011111 1101001010 0010001001
output
69 0 5
限制与约定
对于10%的数据，$n \leq 20, m \leq 30, \ q = 1$
对于另外20%的数据，$n \leq 1000, m \leq 16$
对于另外40%的数据，$n \leq 500, m \leq 1000$
对于100%的数据，$1 \leq n \leq 1000, \ 1 \leq m \leq 5000, \ 1 \leq q \leq 1000$
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
提示
输入文件可能很大，请注意读入效率。
鄂公网安备 42010202000505 号