Bob's Bitwise Operation

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Bob is studying bitwise operation, like bitwise and operation & and bitwise or operation |. Bob was given N binary strings with the length L, a_1, a_2, \ldots, a_N, which consist of only 0 and 1. Bob's teacher gives him another M binary strings with length L, b_1, b_2, \ldots, b_M. For each binary string b_j, Bob's teacher asks him the number of ways to insert N bitwise operations & or | into the sequence 0, a_1, a_2, \ldots, a_N so that the result of the entire expression is equal to b_j. Specially, the leftmost number in the entire expression is 0. In other words, Bob needs to find out the number of ways to insert operations so that 0 \: \text{?} \: a_1 \: \text{?} \: a_2 \: \ldots \: \text{?} \: a_N \: = \: b_j where \text{?} is either & or |. Bob cannot change the order of strings a_1 to a_N.

Note, the bitwise and operation & and the bitwise or operation | have the equal precedence in this problem. When evaluating the expression, Bob will evaluate it from left to right. For example, 1 \,|\, 0 \,\& \,1 = \,(1 | 0)\, \&\, 1 = \, 1 \,\& \, 1 = 1

Since the answer may be very huge, output the number of ways modulo 10^9 + 7.

Input Specification

The first line of input contains three integers N, L and M (1 \le N \le 1000, 1 \le L \le 5000, 1 \le M \le 1000), the number of binary strings Bob has, the length of each binary string, and the number of binary string Bob's teacher gives.

Each of the following N lines contains a binary string a_i with length L which consists of only 0 and 1.

Each fo the following M lines contains a binary string b_i with length L which consists of only 0 and 1.

Output Specification

Output M lines. Each line contains an integer, the number of ways modulo 10^9 + 7.

Constraints

Subtask Points Additional constraints
1 10 N \le 20, L \le 30 and M = 1
2 20 N \le 1000, L \le 16
3 40 N \le 500, L \le 1000
4 30 No additional constraints.

Sample Input 1

3 3 2
001
010
111
011
111

Sample Output 1

1
4

Explanation 1

For the 1st query string 011, there is only one way 0 \:|\: 001 \: |\: 010\: \& \:111\: = \:011

For the 2nd query string 111, Bob can put any opearations for the first two postions and put bitwise or operation at the thrid position. Thus, there are four ways, which are shown as follows.

  1. 0 \:\&\: 001 \: \&\: 010\: | \:111\: = \:111
  2. 0 \:\&\: 001 \: |\: 010\: | \:111\: = \:111
  3. 0 \:|\: 001 \: \&\: 010\: | \:111\: = \:111
  4. 0 \:|\: 001 \: |\: 010\: | \:111\: = \:111

Sample Input 2

5 5 1
01110
11011
10000
01010
00100
00100

Sample Output 2

6

Sample Input 3

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

Sample Output 3

69
0
5

Comments

There are no comments at the moment.