Every year, a university hosts a "Mystery Hunt" event where players must solve clues to find the location of a treasure. The winning team from the previous year earns the opportunity to design the puzzles for the current year.

As a freshman, you are very interested in this event. Every day, you walk from west to east through a long corridor in the teaching building. This corridor is so long that it is jokingly referred to as the "infinite corridor." Once, while walking through this corridor, you noticed $n$ binary numbers of equal length $m$ hidden on the walls. You recorded these numbers from west to east, forming a binary array $a_1, a_2, \dots, a_n$.

Soon after, in the latest issue of Voo Doo magazine, you discovered $q$ binary strings $r_1, r_2, \dots, r_q$, each of length $m$. Being clever, you quickly realized the meaning of these numbers.

Keeping the order of the array $a_1, a_2, \dots, a_n$ unchanged, you can insert either $\wedge$ (bitwise AND) or $\vee$ (bitwise OR) operators between them. For example: $11011 \wedge 00111 = 00011$, and $11011 \vee 00111 = 11111$.

You need to insert exactly $n$ operators: one between each adjacent pair of numbers, and one to the left of the first number. If we prepend a $0$ to the left of the first operator, it forms an expression whose value can be calculated. As usual, the order of operations is from left to right. Interestingly, the puzzle setter has already provided you with the set of possible values for this expression—the binary strings $r_1, r_2, \dots, r_q$ from the Voo Doo magazine. The goal is to calculate, for each value $r_i$ in $r_1, r_2, \dots, r_q$, how many ways there are to fill in these $n$ operators such that the value of the expression is $r_i$.

However, the "infinite corridor" is truly long, which means the data range can be very large. Consequently, the answer can also be very large, but you find that due to the nature of the puzzle, you only need to output the answer modulo $1000000007$ ($10^9 + 7$, a prime number).

Input

The first line contains three integers $n, m, q$, as described in the problem. The next $n$ lines each contain a binary string of length $m$, where the leftmost bit is the most significant bit, representing $a_i$. The next $q$ lines each contain a binary string of length $m$, where the leftmost bit is the most significant bit, representing $r_i$.

Output

Output $q$ lines, each containing one integer, where the $i$-th line represents the answer corresponding to $r_i$.

Examples

Input 1

5 5 1
01110
11011
10000
01010
00100
00100

Output 1

6

Note 1

There are exactly six expressions that evaluate to $00100_2$: (the subscript $2$ indicates that the number is in binary)

$0 \wedge 01110_2 \wedge 11011_2 \vee 10000_2 \wedge 01010_2 \vee 00100_2$ $0 \vee 01110_2 \vee 11011_2 \wedge 10000_2 \wedge 01010_2 \vee 00100_2$ $0 \wedge 01110_2 \vee 11011_2 \wedge 10000_2 \wedge 01010_2 \vee 00100_2$ $0 \vee 01110_2 \wedge 11011_2 \wedge 10000_2 \wedge 01010_2 \vee 00100_2$ $0 \wedge 01110_2 \wedge 11011_2 \wedge 10000_2 \wedge 01010_2 \vee 00100_2$ $0 \vee 01110_2 \vee 11011_2 \vee 10000_2 \vee 01010_2 \wedge 00100_2$

Input 2

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

Output 2

69
0
5

Constraints

For 10% of the data: $n \le 20, m \le 30, q = 1$ For another 20% of the data: $n \le 1000, m \le 16$ For another 40% of the data: $n \le 500, m \le 1000$ For 100% of the data: $1 \le n \le 1000, 1 \le m \le 5000, 1 \le q \le 1000$

Note

The input file may be very large; please pay attention to input efficiency.