K. 杂鱼们的悲惨命运

热爱和平的琦玉老师住在和平的 $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$ 意义下的倒数。

样例输入

2
2 2 1 2
..
X.
3
1 1 2
2 1 2
4 1 1
2 3 1 3
.X.
...
3
1 2 2
2 1 3
3 2 2

样例输出

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$ 为一个质数。