seuOJ173 - 杂鱼们的悲惨命运

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：1000 ms
空间限制：256 MiB
题目标签：春季, 校赛, 2019

题目描述

~~热爱和平的~~琦玉老师住在~~和平的~~ $Z$ 市。这里因为经常有怪人出没，所以房价十分便宜。

整个 $Z$ 市可以看成一个 $n\times m$ 的平面方格，其中有些区域不可达。狼级怪人每个时刻会在可达的地方随机出现一个，并在下一个时刻之前跑到其他市作恶。

$Z$ 市充满怪人的真正原因是，怪人协会的总部设在 $Z$ 市的正下方。为了更好的监控 $Z$ 市、以便随时进攻英雄协会，怪人协会的参谋长大炯眼会派遣 $k$ 个虎级怪人到 $Z$ 市侦查。这些侦查员会在出现的下一时刻之前回到总部汇报情况。

在赶往超市买完特价商品后，琦玉非常无聊，决定到 $Z$ 市中随便走走。琦玉在 $0$ 时刻从 $(s_x,s_y)$ 出发，并在下一时刻随机到达相邻的一个可达区域。如果琦玉在某个时间点遇到了怪人（无论是狼级、虎级），他会留在这个区域、并用普通拳随手解决。

（如果对规则的细节存在疑问，可以参照样例解释）

比作者 $ONE$ 更懂《一击男》的贴吧老哥们决定帮大炯眼算一算，它将期望损失多少名侦查员。

输入格式

第一行有一个正整数 $T(1\leq T\leq 5)$ ，表示数据的组数。

对于每组数据，第一行有四个正整数 $n,\ m(1\le n,\ m\le 20$ ，且保证 $n\times m\le 80),\ s_x,\ s_y$ ，表示 $Z$ 市的大小为 $n\times m$ 、琦玉在 $0$ 时刻的出发点 $(s_x,s_y)$ ，该点一定对应一个可达的区域。

接下来 $n$ 行，每行有 $m$ 个字符，为 "." 或 "X"（不含引号）。"." 表示可通过，"X" 表示不可通过。

第 $n+2$ 行，有一个正整数 $k(1\le k\le 10)$ ，表示大炯眼派出的侦查员的数量。

接下来 $q$ 行，每行有三个正整数 $t_i,\ x_i,\ y_i(1\le t_i\le 30,\ 1\le x_i\le n,\ 1\le y_i\le m)$ ，分别表示侦查员出现的时间为 $t_i$ 、出现在区域 $(x_i,y_i)$ ，数据保证 $t_i$ 单调增、 $(x_i,y_i)$ 一定对应一个可达的区域。

输出格式

对于每组数据，输出一行，为一个整数 $ans$ 。其计算方式为期望损失的侦查员数量 $\frac{p}{q}$ 在模 $1000000007$ 意义下的值。

$\frac{p}{q}$ 可以通过 $p\times \frac{1}{q}$ 计算；其中 $\frac{1}{q}$ 表示 $q$ 在取模意义下的倒数，即有 $q\times \frac{1}{q} \equiv 1(mod\ 1000000007)$ 。

例如： $2\times 500000004=1000000008\equiv 1(mod$ $1000000007)$ ，所以 $500000004$ 是 $2$ 在模 $1000000007$ 意义下的倒数。

样例

样例输入

样例输出

320987658
64000001

样例解释

对于样例一，琦玉在时间 $1$ 到达 $(1,1)$ 、 $(1,2)$ 、 $(2,2)$ 的概率都为 $\frac{1}{3}$ 。

在时间 $2$ ，这个概率分别为 $\frac{1}{9}$ 、 $\frac{7}{9}$ 、 $\frac{1}{9}$ 。

在时间 $3$ ，这个概率分别为 $\frac{1}{27}$ 、 $\frac{25}{27}$ 、 $\frac{1}{27}$ 。

在时间 $4$ ，这个概率分别为 $\frac{26}{81}$ 、 $\frac{29}{81}$ 、 $\frac{26}{81}$ 。

所以总的期望值为 $\frac{1}{3}+\frac{7}{9}+\frac{26}{81}=\frac{116}{81}$ ，在模 $1000000007$ 意义下为 $320987658$ 。

提示

通过费马小定理可以得到： $a^{p}\equiv a (mod$ $p)$ ，其中 $p$ 为一个质数。