P4424 [HNOI/AHOI2018] Treasure Hunt

At a certain university, there is an annual Mystery Hunt. Players must solve puzzles using given clues to find the treasure, and the previous year's winning team earns the right to write the problems for the current year. As a freshman, you are very interested in this event. Every day you walk from west to east through a very long corridor in the teaching building. The corridor is so long that people jokingly call it the "infinite corridor." One day, as you pass through the corridor, you notice that there are $n$ hidden binary numbers of equal length on the corridor wall, all of length $m$. You record these numbers from west to east, forming a binary array of $n$ numbers $a_1,a_2,...,a_n$. Soon, in the latest issue of the Voo Doo magazine, you discover $q$ binary numbers of length $m$, namely $r_1,r_2,...,r_q$. You quickly figure out the meaning of these numbers. Keeping the order of the array $a_1,a_2,...,a_n$ unchanged, you may insert $\land$ (bitwise AND) or $\lor$ (bitwise OR) between them. For example: $11011\land 00111=00011$, $11011\lor 00111=11111$. You need to insert $n$ operators: exactly one between each pair of adjacent numbers, and one more to the left of the first number. If we put a $0$ to the left of the first operator, this forms an expression whose value we can compute. As usual, the evaluation order is from left to right. Interestingly, the setter has already told you the possible set of resulting values — the binary numbers $r_1,r_2,...,r_q$ in the Voo Doo magazine. The way to solve the puzzle is: for each value $r_i$ among $r_1,r_2,...,r_q$, compute how many ways there are to fill in these $n$ operators so that the expression evaluates to $r_i$. However, the infinite corridor is truly long, which means the ranges may be very large. Therefore, the answers may also be very large, but due to the special nature of the puzzle, you only need to output the answers modulo $1000000007$.

The first line contains three integers $n,m,q$, as described. The next $n$ lines: the $i$-th line contains a binary number of length $m$, with the most significant bit on the left, representing $a_i$. The next $q$ lines: the $i$-th line contains a binary number of length $m$, with the most significant bit on the left, representing $r_i$.

Output $q$ lines, one integer per line. The $i$-th line is the answer for $r_i$.

Constraints: - For $10\%$ of the testdata, $n \le 20$, $m \le 30$, $q = 1$. - For an additional $20\%$ of the testdata, $n \le 1000$, $m \le 16$. - For an additional $40\%$ of the testdata, $n \le 500$, $m \le 1000$. - For all testdata, $1 \le n \le 1000$, $1 \le m \le 5000$, $1 \le q \le 1000$. Translated by ChatGPT 5