Pony Running

Ponyville has been controlled by the changelings! The ponies are too scared to move. Fortunately, there is still a magic area in Ponyville to protect the ponies.

The magic area is an $n\times m$ grid. We denote the grid in the $x$-th row and $y$-th column by $(x, y)$. For each second, the ponies can move up, down, left, or right with different possibilities. Formally, if a pony locates at $(x, y)$, then in the next second, he will move up to $(x-1, y)$ with the probability of $p_{xy0}$, or move down to $(x+1, y)$ with the probability of $p_{xy1}$, or move left to $(x, y-1)$ with the probability of $p_{xy2}$, or move right to $(x, y+1)$ with the probability of $p_{xy3}$. It's possible for the ponies to move out of the magic area (for example, a pony locates at a grid in the first row, and he moves up in the next second). Since it's very dangerous to move out of the magic area, the ponies would like to know what's the sum of the mathematical expectation of the time for each pony to move out of the area.

There are $q$ events. The first kind of event is to change the probabilities for the four directions in a grid. The second kind of event is to place a pony in each grid, then query the sum of the mathematical expectation of the time for each pony to move out of the area.

The first line of input contains three integers $n, m, q$ $(1 \le n,m,q \le 400, 1\le n \times m \le 400)$, indicating the number of rows and columns of the grid, and the number of events.

For the next $n \times m$ lines, the $((i-1)\times m+j)$-th line contains $4$ integers $p_{ij0},\ p_{ij1}, p_{ij2}, p_{ij3}$ $(0\leq p_{ij0}, p_{ij1}, p_{ij2}, p_{ij3}< 1,000,000,007)$, indicating the probabilities for the pony that locates at $(i, j)$ to move up, down, left, and right. The probabilities are given in the form of modulo $1,000,000,007$. That is, if the probability is $P/Q$, then the given integer is $P\cdot Q^{-1}\pmod {1,000,000,007}$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $1,000,000,007$. It's guaranteed that $p_{ij0}+p_{ij1}+p_{ij2}+p_{ij3}\equiv 1 \pmod{1,000,000,007}$.

For the next $m$ lines, each line represents an event.

• $1\ x\ y\ p_0\ p_1\ p_2\ p_3$, indicating that the four probabilities of the gird $(x, y)$ will be changed to $p_0\ p_1\ p_2\ p_3$. $(1\leq x\leq n, 1\leq y\leq m, 0\leq p_0, p_1, p_2, p_3<1,000,000,007, p_0+p_1+p_2+p_3 \equiv 1 \pmod{1,000,000,007})$


• $2$, indicating to query the sum of the mathematical expectation of the time for each pony to move out of the area.

For each query, output the answer modulo $1,000,000,007$ in a single line. That is, if the answer is $P/Q$, you should output $P\cdot Q^{-1} \pmod{1,000,000,007}$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $1,000,000,007$.

2 2 5
500000004 0 500000004 0
500000004 0 500000004 0
500000004 0 500000004 0
500000004 0 500000004 0
2
1 1 1 0 500000004 0 500000004
2
1 1 2 0 500000004 0 500000004
2

500000010
14
14

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）