Given a maze with N rows and M columns, where represents the cell on the i-row, j-th column. If , it's a wall and can't not be passed. If you are on the cell , you can go to , , or as long as it's not a wall.

Sometime, a cell may be changed into wall, or vise versa. You need to find out the number of way to pass through the maze starting at some given cell and finishing at some given cell.

If the starting cell or finishing cell is a wall, there's clearly no way to pass through the maze.

Note that you can't go back to the cell you just from.

输入描述:

The first line of input contains three space-separated integers N, M, Q.
Following N lines each contains M characters  representing the maze.
Following Q lines each contains three space-separated integers .

If , the state of cell  is changed.
If , you need to find out the number of way to start at cell  and finish at cell .





If ,  and .
If , .

输出描述:

For each , Output one line containing an integer representing the answer module .

2 2 3
00
00
2 1 2
1 1 2
2 1 2

2
1