Dreamy Putata
Putata 梦见自己迷失在一个 n×m 的幻影网格世界里。行编号为 0,1,…,n−1,列编号为 0,1,…,m−1。他不知道怎样逃离,于是决定随机行走。
当 Putata 位于 (x,y) 时,他每一步按下列概率移动:
- 以 ℓ(x,y)/100 的概率到达 (x,(y−1)modm);
- 以 r(x,y)/100 的概率到达 (x,(y+1)modm);
- 以 u(x,y)/100 的概率到达 ((x−1)modn,y);
- 以 d(x,y)/100 的概率到达 ((x+1)modn,y)。
这里取模的结果始终在 0 到模数减一之间;上下边界相接,左右边界也相接。
你需要依次执行 q 次操作:
1 x y c_l c_r c_u c_d:把该格子的四个整数概率参数依次改为 cℓ,cr,cu,cd。保证 0≤x<n、0≤y<m,每个参数在 [1,100] 内,且四个参数之和为 100。
2 sx sy tx ty:Putata 从 (sx,sy) 出发,询问他第一次到达 (tx,ty) 所需步数的期望。保证两个位置不同,所有坐标均在相应范围内。
请回答所有第二类操作。
输入格式
第一行包含两个整数 n,m,满足 3≤n≤105、3≤m≤5。
接下来的 4n 行分为四个连续的部分,每部分各有 n 行,每行 m 个整数。四部分依次给出 ℓ、r、u、d 的全部参数:每部分第 i 行(1≤i≤n)对应网格第 i−1 行,依列编号从 0 到 m−1 排列。每个整数均在 [1,100] 内,且对于每个格子都有
ℓ(x,y)+r(x,y)+u(x,y)+d(x,y)=100.
然后一行包含整数 q,满足 1≤q≤3⋅104。
最后 q 行依次描述操作,格式如上。所有修改立即生效,后续询问使用当前的参数。
输出格式
每个第二类操作输出一行,表示所求期望在模 P=109+7 意义下的值。
准确地说,若期望约分后为 a/b,输出满足 br≡a(modP) 的最小非负整数 r。原题保证对于每个所询问的答案,这样的 r 总是存在,因此答案唯一且位于 [0,P−1]。
这个保证针对约分后的被询问答案,不能改写为“某个模线性方程组必定可逆”,也不要求没有被询问的其他起点的期望均能在模 P 下表示。
原样例
输入:
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