There is a rectangular lake with N rows and M columns and you are standing on a stone in the top left corner (1, 1) of the lake and you want to go to the stone at the bottom right corner (N, M). You can consider the lake as a 2D grid. But there is a problem. You can only jump to adjacent right and bottom cell from the current one. You are wearing your new year dress and don't want to get wet. So you only will jump from one stone to another stone.
But you are a stubborn lad. And you have some lucky cells. And you say, if you want to cross the lake then you at least have to go through at least one of your lucky cells otherwise you won't go through that path.
You are given the lake's dimension and the grid. "#" means a stone and "." means water.
Now you are given Q queries. In every query, you are given the lucky cell's positions. For each query you need to output the number of paths that you can follow to get to the bottom right corner.
Input
The first line will contain two integer N and M, number of rows and columns.
Then there will be N lines each having M characters representing the lake.
Then Q which is the number of queries.
For each query, the first line will be L the number of lucky cells.
Next L lines. The ith line will contain (xi, yi).
1 ≤ N * M ≤ 106
1 ≤ Q ≤ 2000
1 ≤ L ≤ 1000
1 ≤ xi+1 < xi ≤ N
1 ≤ yi-1 < yi ≤ M
Output
For each query, print the number of paths explained above.
As the number can be very big print the answer modulo 1000000007 (109 + 7).
Sample
| Input | Output |
|---|---|
2 2 ## .# 2 1 1 2 1 2 1 | 1 0 |
