【HNOI2018】寻宝游戏 - 题目 - Universal Online Judge

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

作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为Infinite Corridor。一次，你经过这条走廊的时候，注意到在走廊的墙壁上隐藏着 $n$ 个等长的二进制的数字，长度均为 $m$ 。你从西向东将这些数字记录了下来，形成一个含有 $n$ 个数的二进制数组 $a_{1}, a_{2} \dots, a_{n}$ 。

很快，在最新的一期Voo Doo杂志上，你发现了 $q$ 个长度也为 $m$ 的二进制串 $r_{1}, r_{2}, \dots, r_{q}$ 。

聪明的你很快发现了这些数字的含义。

保持数组 $a_{1}, a_{2} \dots, a_{n}$ 的元素顺序不变，你可以在它们之间插入 $\land$ （按位与运算）或者 $\lor$ （按位或运算）两种二进制运算符。例如： $11011 \land 00111 = 00011 ， 11011 \lor 00111 = 11111$ 。

你需要插入恰好 $n$ 个运算符，相邻两个数之间恰好一个，在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个0，这就形成了一个运算式，我们可以计算它的值。与往常一样，运算顺序是从左往右。有趣的是，出题人已经告诉你这个值的可能的集合——Voo Doo杂志里的那一些二进制数 $r_{1}, r_{2}, \dots, r_{q}$ ，而解谜的方法，就是对 $r_{1}, r_{2}, \dots, r_{q}$ 中的每一个值 $r_{i}$ ，分别计算出有多少种方法填入这 $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

output

explanation

有以下且仅有以下六个运算式的值是 $00100_{2}$ ：(下标2表示被标识的数是二进制数)

$0 \land 01110_{2} \land 11011_{2} \lor 10000_{2} {\land 01010}_{2} {\lor 00100}_{2}$

$0 \lor 01110_{2} {\lor 11011}_{2} \land 10000_{2} {\land 01010}_{2} {\lor 00100}_{2}$

$0 \land 01110_{2} {\lor 11011}_{2} \land 10000_{2} {\land 01010}_{2} {\lor 00100}_{2}$

$0 \lor 01110_{2} \land 11011_{2} \land 10000_{2} {\land 01010}_{2} {\lor 00100}_{2}$

$0 \land 01110_{2} {\land 11011}_{2} \land 10000_{2} {\land 01010}_{2} {\lor 00100}_{2}$

$0 \lor 01110_{2} \lor 11011_{2} \lor 10000_{2} {\lor 01010}_{2} {\land 00100}_{2}$

样例二

input

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 s$

空间限制： $512 MB$

提示

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

下载

样例数据下载

Universal Online Judge

UOJ

#384. 【HNOI2018】寻宝游戏

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

限制与约定

提示

下载