延时操控

Problem Description

给定一张 $n$ 行 $n$ 列的网格地图，其中 '#' 表示障碍，剩下的字符表示空地。地图上有恰好一名己方角色 '$\texttt{P}$' 和敌方角色 '$\texttt{E}$'。 你需要帮助小Q操控己方角色去击败敌方角色成功通关游戏。在每一回合中，你需要键入恰好一个字符以表示操作指令，分为以下四种：

• '$\texttt{L}$': 从 $(x,y)$ 移动至 $(x,y-1)$。
• '$\texttt{R}$': 从 $(x,y)$ 移动至 $(x,y+1)$。
• '$\texttt{U}$': 从 $(x,y)$ 移动至 $(x-1,y)$。
• '$\texttt{D}$': 从 $(x,y)$ 移动至 $(x+1,y)$。 如果目的地是障碍或者不在地图内，那么本次移动将会失败。己方角色可以与敌方角色重叠，也可以穿透对方。一旦移动失败，移动方将扣除 $1$ 点生命值，并在这一回合待在原地。由于小Q选的是最高难度，因此己方没有任何容错率，而敌方有 $hp$ 点生命值。敌方不会自主移动，只会复读己方 $k$ 回合之前的指令，你需要善用该机制来''延时操控''敌方以获得胜利。 游戏即将从第 $1$ 回合开始，一共执行 $m$ 个回合；第 $i$ 回合的执行逻辑如下： 1、键入第 $i$ 回合的操作指令 $c_i$。 2、尝试按照指令 $c_i$ 移动己方角色，若移动失败则游戏立即结束。 3、（若 $i\leq k$ 则忽略本条）尝试按照指令 $c_{i-k}$ 移动敌方角色，若移动失败则敌方角色扣除 $1$ 点生命值，若生命值为 $0$ 则游戏立即通关。 请写一个程序，统计有多少种可能的操作序列使得你可以通关游戏。两个操作序列被认为不同当且仅当长度不同或者某一回合的指令不同。请注意：如果第 $m$ 回合仍然没有将敌方的生命值归零，则这样的方案不满足条件。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 100$)，表示测试数据的组数。 每组数据第一行包含四个整数 $n,m,k,hp$ ($2\leq n\leq 50$, $1\leq m\leq 50$, $0\leq k < m$, $1\leq hp\leq 5$)，分别表示地图的尺寸、总回合数、延时回合数以及敌方的生命值。 接下来 $n$ 行，每行一个长度为 $n$ 的字符串，由 '#'、'$\texttt{.}$'、'$\texttt{P}$'、'$\texttt{E}$' 构成，描述地图。输入数据保证恰好存在一个 '$\texttt{P}$' 和一个 '$\texttt{E}$'。 输入数据保证最多只有 $10$ 组数据满足 $n > 20$。

Output

对于每组数据输出一行一个整数，即能通关的操作序列数量，由于答案可能很大，请对 $10^9+7$ 取模输出。

Sample Input

2
2 3 0 2
.#
PE
5 5 2 1
.....
...P.
.....
.E...
.....

Sample Output

1
124

Hint

对于第一组样例，满足条件的操作序列只有一组：''$\texttt{UD}$''。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）