CODESPTD - Queens on a Board

no tags 

You have an N × M chessboard on which some squares are blocked out. In how many ways can you place one or more queens on the board such that no two queens attack each other? Two queens attack each other if one can reach the other by moving horizontally, vertically or diagonally without passing over any blocked square. At most one queen can be placed on a square. A queen cannot be placed on a blocked square.

Input

The first line contains the number of test cases T. T test cases follow. Each test case contains integers N and M on the first line. The following N lines contain M characters each representing the board. A '#' represents a blocked square and a '.' represents an unblocked square.

Output

Output T lines containing the required answer for each test case. As the answers can be really large, output them modulo 1000000007.

Constraints

1 ≤ T ≤ 100

1 ≤ N ≤ 50

1 ≤ M ≤ 5

Exaample

Input:
4
3 3
...
...
...
3 3
.#.
.#.
...
2 4
.#..
....
1 1
#

Output:
17
18
14
0

hide comments
:D: 2012-05-30 11:25:37

Samples are definitively correct. If you think there should be more, write out all layouts for 2 queens or more (1 is trivial) for test case no 3. If you can get 8, it will prove cases wrong. There is no easy way to "explain" it without enumerating, since that's the topic of this problem.

Samuel Shen: 2012-02-24 10:39:57

i am not getting the how testcases are right???
for each of the testcases my solution is giving more ways than yours.....
very first thing is to place single queen at every position and then try for 2 queens and so on....
please explain if wrong


Added by:Varun Jalan
Date:2011-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest