UOJ Logo Universal Online Judge

UOJ

#384. 【HNOI2018】寻宝游戏

统计

某大学每年都会有一次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}$

提示

输入文件可能很大,请注意读入效率。

下载

样例数据下载