401821: GYM100534 D Coin Table

Eli has got a square board as his birthday present. Some cells of this board are filled with coins and other cells are empty. Rashof (her Russian bear doll) is capable of collecting coins and can go right or down. She will put Rashof in the top-left cell of the table. If a rectangle of the table is blocked, which means Rashof can not pass or land on that rectangle at all, how many ways can Rashof take maximum number of coins and reach lower-right cell of the board?

Each test case contains one positive integer n, the size of the board. Each of the next n lines contain n characters, '.' or 'C'. '.' is an empty cell and 'C' is a coin. The next line contains Q, the number of queries. Each of the next Q lines contains four integers, r1, c1, r2 and c2, which are the top-left and bottom-right cells of the blocked rectangle. For each query print the number of ways Rashof can take maximum number of coins. 1 ≤ n ≤ 1000 0 ≤ r1, c1, r2, c2 ≤ n - 1 1 ≤ Q ≤ 1000

For each query print two space separated integers, the maximum number of coins Rashof can take without passing the blocked rectangle, and the number of ways it can do that modulo 1000000007.

6
C...CC
CC..C.
..C...
CCC.C.
CCC.CC
CC...C
3
2 2 2 2
1 0 4 2
4 4 5 5

9 7
7 1
0 0