AVOIDSOS - Avoiding SOS Grids


You are given a grid having N rows and M columns. Some squares are contain letters 'S' or 'O', whereas the other squares are unfilled. A filled grid is called "Avoiding SOS" if there is no occurrence of the string "SOS" in the grid either vertically or horizontally. In how many ways can the grid be completed by filling the unfilled squares with either 'S' or 'O' such that the resultant grid is "Avoiding SOS"?

Input

The first line contains T the number of test cases. T test cases follow.

The first line for each test case contains N and M, the number of rows and columns in the grid respectively.

N lines follow, each containing M characters. The jth character in the ith line is a '.' if the corresponding square in the grid is unfilled, otherwise it contains either the letter 'S' or the letter 'O'. A blank line separates two test cases.

Output

Output T lines, one for each test case, containing the desired answer for the corresponding test case. Output each result modulo 1000000007.

Example

Input:
5
2 3
...
...

1 4
....

3 3
.O.
S.S
.O.

1 3
SOS

1 3
SOO

Output
49
12
9
0
1

Constraints

1 ≤ T ≤ 100
1 ≤ N, M ≤ 8


hide comments
:D: 2012-12-08 20:26:32

Yes, it's seems to be pretty hard to optimise. I Felt I done a decent job, but ended up with average time.

Mine complexity could be upper bounded with O(2^(2N) * N), but should speed up a lot with even minor number of fields set.

Anil Kishore: 2010-09-28 07:08:25

O( 2^(2n) x n^2 x 2 ) giving TLE :( . Need a better algo I guess, or is the constant high ?


Added by:Varun Jalan
Date:2010-07-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:own problem used for Indian ICPC training camp