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
.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints. |
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
Comments