loj#P2494. 「AHOI / HNOI2018」寻宝游戏

「AHOI / HNOI2018」寻宝游戏

题目描述

某大学每年都会有一次 Mystery Hunt 的活动,玩家需要根据设置的线索解谜,找到宝藏的位置,前一年获胜的队伍可以获得这一年出题的机会。

作为新生的你对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊,这条走廊是如此的长,以至于它被人戏称为 infinite corridor。一次,你经过这条走廊的时,注意到在走廊的墙壁上隐藏着 nn 个等长的二进制的数字,长度均为 mm。你从西向东将这些数字记录了下来,形成一个含有 nn 个数的二进制数组 a1,a2,...,ana_1, a_2, ..., a_n。很快,在最新的一期 Voo Doo 杂志上,你发现了 qq 个长度也为 mm 的二进制串 r1,r2,...,rqr_1, r_2, ..., r_q。聪明的你很快发现了这些数字的含义。保持数组 a1,a2,...,ana_1, a_2, ..., a_n 的元素顺序不变,你可以在它们之间插入 \wedge(按位与运算)或者 \vee(按位或运算)两种二进制运算符。例如:1101100111=00011,1101100111=1111111011 \wedge 00111=00011,11011 \vee 00111=11111

你需要插入恰好 nn 个运算符,相邻两个数之间恰好一个,在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个 00,这就形成了一个运算式,我们可以计算它的值。与往常一样,运算顺序是从左往右。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo 杂志里的那一些二进制数 r1,r2,...,rqr_1, r_2, ..., r_q,而解谜的方法,就是对 r1,r2,...,rqr_1, r_2, ..., r_q 中的每一个值 rir_i,分别计算出有多少种方法填入这 nn 个运算符,使得这个运算式的值是 rir_i 。然而,infinite corridor 真的很长,这意味着数据范围可能非常大。因此,答案也可能非常大,但是你发现由于谜题的特殊性,你只需要求答案模 10000000071000000007109+710^9 + 7,一个质数)的值。

输入格式

第一行三个数 n,m,qn, m, q,含义如题所述。

接下来 nn 行,其中第 ii 行有一个长度为 mm 的二进制串,左边是最高位,表示 aia_i

接下来 qq 行,其中第 ii 行有一个长度为 mm 的二进制串,左边是最高位,表示 rir_i

输出格式

输出 qq 行,每行一个数,其中第 ii 行表示对应于 rir_i 的答案。

5 5 1
01110
11011
10000
01010
00100
00100
6
10 10 3
0100011011
0110100101
1100010100
0111000110
1100011110
0001110100
0001101110
0110100001
1110001010
0010011101
0110011111
1101001010
0010001001
69
0
5

数据范围与提示

对于 10%10\% 的数据,n20,m30n \le 20, m \le 30q=1q = 1

对于另外 20%20\% 的数据,n1000n \le 1000m16m \le 16

对于另外 40%40\% 的数据,n500n \le 500m1000m \le 1000

对于 100%100\% 的数据,1n10001 \le n \le 10001m50001 \le m \le 50001q10001 \le q \le 1000