题目描述

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

Sample Input

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

Sample Output

69
0
5

[LOJ2494][AHOI/HNOI2018]寻宝游戏

原文：https://www.cnblogs.com/yich/p/12016977.html