Go
Recently, the Go AI developed by Google, AlphaGo, defeated former world champion Lee Sedol with a score of 4:1, marking another milestone in the field of artificial intelligence. Unlike traditional search-based AI, AlphaGo uses the recently popular convolutional neural network model.
In a convolutional neural network model, every region of a specific size on the board is treated as a window. For example, if the board size is $5 \times 6$ and the window size is $2 \times 4$, there are a total of 12 windows on the board. Furthermore, the model has pre-defined templates, where the size of the template is the same as the size of the window. The figure below shows a $5 \times 6$ board and two $2 \times 4$ templates. For a given template, if there is any window on the board that matches it perfectly, we say that this template is activated; otherwise, we say that the template is not activated. For example, the first template in the figure is activated, while the second template is not.
The problem we want to study is: for a given template, how many boards can activate it?
To simplify the problem, we set aside all the basic rules of Go and only consider an $n \times m$ board, where each position can be one of three states: black stone, white stone, or no stone. In other words, there are $3^{n \times m}$ such boards. Additionally, we will provide $q$ templates of size $2 \times c$. We want to know, for each template, how many boards can activate it.
Emphasis: The templates are always two rows high.
Input
The first line of the input contains four positive integers $n$, $m$, $c$, and $q$, representing the number of rows on the board, the number of columns on the board, the number of columns in the templates, and the number of templates, respectively.
Following this are $2 \times q$ lines, with every two consecutive lines describing a template. Each line contains $c$ characters, which are always one of 'W', 'B', or 'X', representing a white stone, a black stone, or no stone, respectively.
Output
The output should contain $q$ lines, each containing an integer representing the number of boards that satisfy the requirements. Since the answer may be very large, you only need to output the result modulo $1,000,000,007$.
Examples
Input 1
3 1 1 2 B W B B
Output 1
6 5
Input 2
3 3 2 3 XB BW BX XB BB BB
Output 2
963 954 857
Note
Explanation for Example 1: Boards that can activate BW: BWB, BWW, BWX, BBW, WBW, XBW (total 6). Boards that can activate BB: BBB, BBW, BBX, WBB, XBB (total 5).
Constraints
| Test Case ID | Constraints |
|---|---|
| 1 | $n=3, m=4, c=2$ |
| 2 | $n=4, m=4, c=3$ |
| 3 | $n=2, m=9, c=6$ |
| 4 | $n=2, m=12, c=3$ |
| 5 | $n=2, m=12, c=5$ |
| 6 | $n=10, m=8, c=3$ |
| 7 | $n=10, m=10, c=5$ |
| 8 | $n=100, m=10, c=5$ |
| 9 | $n=100, m=12, c=5$ |
| 10 | $n=100, m=12, c=6$ |
For all test cases, $q \le 5$.