## Bob's Bitwise Operation

View as PDF

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 binary strings with the length , , which consist of only and . Bob's teacher gives him another binary strings with length , . For each binary string , Bob's teacher asks him the number of ways to insert bitwise operations & or | into the sequence so that the result of the entire expression is equal to . Specially, the leftmost number in the entire expression is . In other words, Bob needs to find out the number of ways to insert operations so that where is either & or |. Bob cannot change the order of strings to .

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,

Since the answer may be very huge, output the number of ways modulo .

#### Input Specification

The first line of input contains three integers , and (, , ), 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 lines contains a binary string with length which consists of only and .

Each fo the following lines contains a binary string with length which consists of only and .

#### Output Specification

Output lines. Each line contains an integer, the number of ways modulo .

, and
,
,

#### Sample Input 1

3 3 2
001
010
111
011
111

#### Sample Output 1

1
4

#### Explanation 1

For the st query string , there is only one way

For the nd query string , 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.

#### 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