题目描述

Given a maze with N rows and M columns, where $b_{ij}$ represents the cell on the i-row, j-th column. If $b_{i, j} = \texttt{"1"}$,j​="1", it's a wall and can't not be passed. If you are on the cell $b_{i, j}$you can go to $b_{(i+1), j}$​,$b_{i, (j-1)}$​, or $b_{i, (j+1)}$ 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 $b_{ij}$ representing the maze. Following Q lines each contains three space-separated integers $q_i, a_i, b_i$​.

If $q_i = 1$, the state of cell $b_{a_i, b_i}$ is changed. If qi=2q_i = 2qi​=2, you need to find out the number of way to start at cell $b_{1, a_i}$​​ and finish at cell $b_{N, b_i}$​​.

输出格式

For each $q_i = 2$, Output one line containing an integer representing the answer module $10^9+7(1000000007)$.

样例

样例输入 1

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

样例输出 1

2
1

数据范围与提示

1≤N,Q≤50000

$1 \leq M \leq 10$

$b_{ij} \in \texttt{"01"}$

$1 \leq q_i \leq 2$

If $q_i = 1$, $1 \leq a_i \leq N$ and $1 \leq b_i \leq M$

If $q_i = 2$, $1 \leq a_i, b_i \leq M$.