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

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

输出q行,每行一个数,其中第i行表示对应于ri的答案

【样例说明】
有以下且仅有以下六个运算式的值是001002:(下标 2 表示被标识的数是二进制数) 

[数据范围]
对于10%的数据,n≤ 20,m ≤ 30, q= 1
对于另外 20%的数据,n≤ 1000, m≤ 16
对于另外 40%的数据,n≤ 500, m≤ 1000
对于 100%的数据,1 ≤n ≤ 1000, 1 ≤ m≤ 5000, 1 ≤ q ≤ 1000

排序 进制转换 AHOI高中 2018 level7