[HNOI/AHOI2018]寻宝游戏

题目描述

某大学每年都会有一次Mystery Hunt的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会。 作为新生的你,对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条走廊是如此的长,以至于它被人戏称为infinite corridor。一次,你经过这条走廊时注意到在走廊的墙壁上隐藏着$n$个**等长的**二进制的数字,长度均为$m$。你从西向东将这些数字记录了下来,形成一个含有$n$个数的二进制数组$a_1,a_2,...,a_n$。 很快,在最新的一期的Voo Doo杂志上,你发现了$q$个长度也为$m$的二进制数$r_1,r_2,...,r_q$。 聪明的你很快发现了这些数字的含义。 保持数组$a_1,a_2,...,a_n$的元素顺序不变,你可以在它们之间插入$∧$(按位与运算)或者$∨$(按位或运算)。例如:$11011∧00111=00011$,$11011∨00111=11111$。 你需要插入$n$个运算符,相邻两个数之前恰好一个,在**第一个数的左边**还有一个。**如果我们在第一个运算符的左边补入一个0**,这就形成了一个运算式,我们可以计算它的值。与往常一样,运算顺序是**从左到右**。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo杂志里的那些二进制数$r_1,r_2,...,r_q$,而解谜的方法,就是对$r_1,r_2,...,r_q$中的每一个值$r_i$,分别计算出**有多少种方法填入这$n$个计算符**,使的这个运算式的值是$r_i$。 然而,infinite corridor真的很长,这意味着数据范围可能非常大。因此,答案也可能非常大,但是你发现由于谜题的特殊性,你只需要求答案模1000000007的值。

输入输出格式

输入格式


第一行三个数$n$,$m$,$q$,含义如题所述。 接下来$n$行,其中第$i$行有一个长度为$m$的二进制数,**左边是最高位**,表示$a_i$。 接下来$q$行,其中第$i$行有一个长度为$m$的二进制数,**左边是最高位**,表示$r_i$。

输出格式


输出$q$行,每行一个数,其中的$i$行表示对于$r_i$的答案。

输入输出样例

输入样例 #1

5 5 1
01110
11011
10000
01010
00100
00100

输出样例 #1

6

输入样例 #2

10 10 3
0100011011
0110100101
1100010100
0111000110
1100011110
0001110100
0001101110
0110100001
1110001010
0010011101
0110011111
1101001010
0010001001

输出样例 #2

69
0
5

说明

对于 10% 的数据,$n \le 20, m \le 30, q = 1$ 对于另外 20 的数据,$n \le 1000, m \le 16$ 对于另外 40 的数据,$n \le 500, m \le 1000$ 对于全部的数据$1≤n≤1000,1≤m≤5000,1≤q≤1000$。。