ENEMY - Eliminate The Enemies

In a modification of the popular game 'Pacman', the player has to move in a two-dimensional grid. Several cells of the grid are blocked. The player can start from any cell that is not blocked and can move in any of the directions, i.e. north, west, south or east, provided that the cells are not blocked.

As soon as the player passes a cell, an enemy is generated in that cell, making it impossible for the player to pass through that cell again. Thus, the player can pass through any given cell only once. The player has to traverse all the unblocked cells in the grid in order to win .

The player can begin at any free cell. Note that the same path with different starting points and even with the same starting point but with different paths of traversal is treated as different routes. The problem requires you to print the total number of all such possible routes.

Input

Each test case starts with a line containing two integers, m and n. Each of the next m lines contain a string of n characters describing the configuration of the grid. '*' denotes a blocked cell and '.' denotes unblocked cells. The input ends with a case having m = 0 and n = 0 and this case need not be processed.

Output

For each test case, print one line containing the total number of possible routes for the corresponding case. As this number can be quite large, you should print ans%1000000007 where ans is the required result.

Example

Input:
3 3
...
.*.
...
3 7
...*...
.*.*.*.
.......
3 3
***
*.*
***
0 0

Output:
16
8
1

Constraints and Limits

m ≤ 100, n ≤ 7, number of test cases ≤ 50


Added by:Ajay Somani
Date:2008-02-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP ERL
Resource:CodeCraft 08, Problem Setter: Jin Bin

hide comments
2022-07-19 17:33:38 [Rampage] Blue.Mary
Data set is really "small", my program will run for ~0.03 second for one largest test case but it gets AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.