Mystery Hunt Expression

A university organizes a yearly Mystery Hunt where teams solve clues to find a treasure. As a newcomer, you become interested in the event and notice that along a long corridor (dubbed the infinite corridor) there are n binary numbers of equal length m engraved on the wall. You record these numbers in order as a₁, a₂, \dots, a_n (each represented by an m-bit binary string).

Soon after, in the latest issue of Voo Doo Magazine, you see q m-bit binary numbers r₁, r₂, \dots, r_q.

You quickly deduce the meaning: by inserting an operator between every two consecutive numbers while keeping the order of the a array, you can form an expression whose value (evaluated from left to right) may equal one of the numbers in \(\{r_1, r_2, \dots, r_q\}\).

The process is as follows. You have exactly n operators to insert. Start by imagining an extra operator placed to the left of the first number; if you prepend a 0 to the left of this operator, an expression is formed. For every slot (there are exactly n slots, between the 0 and \(a_1\), between \(a_1\) and \(a_2\), \(\dots\), between \(a_{n-1}\) and \(a_n\)), you may choose either the bitwise AND operator \(\land\) or the bitwise OR operator \(\lor\>.

In other words, suppose you decide on an operator sequence \(op_1, op_2, \dots, op_n\) where each \(op_i\) is either \(\land\) or \(\lor\). Then, interpreting the expression as:

[ 0; op_1; a_1 ; op_2; a_2 ; \dots ; op_n; a_n, ]

and evaluating it in a left‐to‐right manner (i.e. no operator precedence), you obtain a value. The magazine tells you that the only possible values are exactly the r numbers printed in the magazine.

Your task is: for each binary number \(r_i\) (\(1 \le i \le q\)), count how many ways there are to choose the sequence of operators so that the value of the expression equals \(r_i\). As the numbers may be huge, report each answer modulo \(10^9+7\).

Note: The binary numbers are represented as strings of length m (possibly with leading zeros). The bitwise operations are defined in the usual way and are applied on the m bits simultaneously. For example,
\(11011 \land 00111 = 00011\) and \(11011 \lor 00111 = 11111\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) where \(n\) is the number of binary numbers on the wall, \(m\) is the length of each binary string, and \(q\) is the number of queries.

The following \(n\) lines each contain a binary string of length \(m\), representing \(a_1, a_2, \dots, a_n\).

The next \(q\) lines each contain a binary string of length \(m\) representing \(r_1, r_2, \dots, r_q\).

outputFormat

Output \(q\) lines. The \(i\)th line should contain a single integer, the number of ways (modulo \(10^9+7\)) to choose operators such that the final value of the expression is equal to \(r_i\).

sample

2 3 2
101
110
101
100

0
1

</p>