Little C decided to plant the pattern of CCF in his garden, so he wanted to know how many flowering schemes there are for the two letters C and F; He wants you to help him with this problem.
A garden can be viewed as a grid map with locations, which are the st to th rows from top to bottom, and the st to th columns from left to right, where each location may be mud or not. Specifically, indicates that there is mud at the position of row and column , and indicates that there is no mud at this position.
A planting scheme is called C-shaped, if there exist , and , such that , and , so that the th to th column of the th row, the th to th column of the th row, and the th to th row of the th column are not mud, and flowers are only planted in these positions.
A planting scheme is called F-shaped, if there exist , and , satisfying , and , so that the to column of the row, the to column of the row, and the to row of the column are not mud, and flowers are only planted in these positions.
Sample 1 gives examples of C-shape and F-shape planting schemes.
Now little C wants to know, given , and the value indicating whether each position is mud, how many possibilities are there for C-shaped and F-shaped flowering schemes? Since the answer may be very large, you only need to output the result modulo . Please refer to the output format section for specific output results.
Input Specification
The first line contains two integers , , which respectively represent the number of data sets and the number of test points. All sample data have .
Next, there are sets of data, in each set of data:
The first line contains four integers , , , , where , represent the number of rows and columns of the garden respectively, and see the output format section for the meaning of , .
The next lines, each line contains a string of length and only contains and , where the th character of the th string represents , that is, is the th column of the th row in the garden mud.
Output Specification
For each set of data, if there are and C-shaped and F-shaped flower planting schemes in the garden respectively, you need to output two non-negative integers separated by a space, , and , where represents the result of taking the remainder of divided by .
Sample Input 1
1 0
4 3 1 1
001
010
000
000
Sample Output 1
4 2
Explanation of Sample 1
The four C-typed plans are:
**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***
Where *
means to plant flowers at this position. Note that the two bars of C can be of different lengths.
Similarly, the two F-shape planting schemes are:
**1 **1
*10 *10
**0 ***
*00 *00
Additional Samples
Additional sample cases can be found here.
Constraints
For all data, it is guaranteed that , , , .
Case | Special Property | Points | ||||
---|---|---|---|---|---|---|
1 | 0 | 0 | none | 1 | ||
2 | 1 | 1 | 2 | |||
3 | 3 | |||||
4 | 4 | |||||
5 | 4 | |||||
6 | 6 | |||||
7 | none | 10 | ||||
8 | 6 | |||||
9 | 6 | |||||
10 | 8 | |||||
11 | 10 | |||||
12 | 6 | |||||
13 | 6 | |||||
14 | 8 | |||||
15 | 0 | 6 | ||||
16 | 1 | 14 |
Comments