#P18509. Dreamy Putata

Dreamy Putata

Dreamy Putata

Putata 梦见自己迷失在一个 n×mn\times m 的幻影网格世界里。行编号为 0,1,…,n−10,1,\ldots,n-1,列编号为 0,1,…,m−10,1,\ldots,m-1。他不知道怎样逃离,于是决定随机行走。

当 Putata 位于 (x,y)(x,y) 时,他每一步按下列概率移动:

  • 以 ℓ(x,y)/100\ell(x,y)/100 的概率到达 (x,(y−1) mod m)(x,(y-1)\bmod m);
  • 以 r(x,y)/100r(x,y)/100 的概率到达 (x,(y+1) mod m)(x,(y+1)\bmod m);
  • 以 u(x,y)/100u(x,y)/100 的概率到达 ((x−1) mod n,y)((x-1)\bmod n,y);
  • 以 d(x,y)/100d(x,y)/100 的概率到达 ((x+1) mod n,y)((x+1)\bmod n,y)。

这里取模的结果始终在 00 到模数减一之间;上下边界相接,左右边界也相接。

你需要依次执行 qq 次操作:

  • 1 x y c_l c_r c_u c_d:把该格子的四个整数概率参数依次改为 cℓ,cr,cu,cdc_\ell,c_r,c_u,c_d。保证 0≤x<n0\le x<n、0≤y<m0\le y<m,每个参数在 [1,100][1,100] 内,且四个参数之和为 100100。
  • 2 sx sy tx ty:Putata 从 (sx,sy)(s_x,s_y) 出发,询问他第一次到达 (tx,ty)(t_x,t_y) 所需步数的期望。保证两个位置不同,所有坐标均在相应范围内。

请回答所有第二类操作。

输入格式

第一行包含两个整数 n,mn,m,满足 3≤n≤1053\le n\le 10^5、3≤m≤53\le m\le5。

接下来的 4n4n 行分为四个连续的部分,每部分各有 nn 行,每行 mm 个整数。四部分依次给出 ℓ\ell、rr、uu、dd 的全部参数:每部分第 ii 行(1≤i≤n1\le i\le n)对应网格第 i−1i-1 行,依列编号从 00 到 m−1m-1 排列。每个整数均在 [1,100][1,100] 内,且对于每个格子都有

ℓ(x,y)+r(x,y)+u(x,y)+d(x,y)=100.\ell(x,y)+r(x,y)+u(x,y)+d(x,y)=100.

然后一行包含整数 qq,满足 1≤q≤3⋅1041\le q\le3\cdot10^4。

最后 qq 行依次描述操作,格式如上。所有修改立即生效,后续询问使用当前的参数。

输出格式

每个第二类操作输出一行,表示所求期望在模 P=109+7P=10^9+7 意义下的值。

准确地说,若期望约分后为 a/ba/b,输出满足 br≡a(modP)br\equiv a\pmod P 的最小非负整数 rr。原题保证对于每个所询问的答案,这样的 rr 总是存在,因此答案唯一且位于 [0,P−1][0,P-1]。

这个保证针对约分后的被询问答案,不能改写为“某个模线性方程组必定可逆”,也不要求没有被询问的其他起点的期望均能在模 PP 下表示。

原样例

输入:

4 3
1 2 3
4 5 6
7 8 9
10 11 12
23 24 25
26 27 28
29 30 31
32 33 34
10 11 12
13 14 15
16 17 18
19 20 21
66 63 60
57 54 51
48 45 42
39 36 33
4
2 0 1 1 1
2 0 0 3 2
1 1 1 25 25 25 25
2 0 0 3 2

输出:

76426175
344136684
555192113