消除方块

题号：NC282101
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 行 $m$ 列边长都相等的正方体，位于从上往下数的第 $i$ 行和从左往右数的第 $j$ 列的方块用坐标 ( $i,j$ ) 表示。每个方块上面都有一个字符，字符是所有大写字母、所有小写字母和所有数字之中的一个，最多 $62$ 种字符，不同位置的方块上的字符都不同，记所有方块上的字符组成的集合为 $A$ 。

再给出 $k$ 个长度不小于 $3$ 的字符串，每个字符串都由上述 $A$ 中的部分字符组成，使得 $A$ 中的所有字符恰好在这 $k$ 个字符串中出现一次。

考虑一个从 $1$ 到 $k$ 的排列 $P$ ，称 $P$ 是消除序列当且仅当由 $P$ 生成的下列 $k$ 次操作可以被执行完成且所有方块都将被消除，每次操作包含三步，对于第 $i$ 次操作的三个步骤描述如下：

1. 删除方块：记 $S$ 表示 $k$ 个字符串中的第 $P_i$ 个字符串，考虑长度为 $|S|$ 的序列 $a_1,a_2,\cdots,a_{|S|}$ ，其中第 $j$ 个元素 $a_j$ 表示字符 $S_j$ 对应的方块对应的位置 ( $r_j,c_j$ )，若存在 $j$ ( $2\le j\le |S|$ )使得 $a_{j-1}$ 和 $a_j$ 的曼哈顿距离大于 $1$ 则包括该操作内的后续所有操作都将停止。否则对于每个 $j$ ( $1\le j\le |S|$ )，删除位于 ( $r_j,c_j$ ) 的方块。
2. 上下整理：对于每个 $r$ ( $2\le r\le n$ )和每个 $c$ ( $1\le c\le m$ )，如果 ( $r,c$ ) 存在方块而 ( $r-1,c$ ) 不存在方块，则将该方块移动到 ( $r-1,c$ )。持续做这一步直到所有方块上方没有空位，即对于任意上述 ( $r,c$ )，如果存在方块，则 ( $r-1,c$ ) 也应存在方块。
3. 左右整理：对于每个 $c$ ( $2\le c\le m$ )，如果第 $c-1$ 列不存在方块，则对每个 $r$ ( $1\le r\le n$ )，如果 ( $r,c$ ) 存在方块则将其移动到 ( $r,c-1$ ) 。持续做这一步直到不存在一列没有方块而它的右边一列还有方块，即对于上述 $c$ ，如果第 $c-1$ 列不存在方块，则第 $c$ 列也不存在方块。

对于当前摆放的这 $n$ 层 $m$ 列方块和这 $k$ 个字符串，请求出有多少个不同的消除序列。由于答案可能会很大，请输出答案在 $10^9+7$ 模意义下的结果。

两个数对 ( $r_1,c_1$ ) 和 ( $r_2,c_2$ ) 的曼哈顿距离是指 $|r_1-r_2|+|c_1-c_2|$ 。

输入描述:

第一行输入两个正整数 ,，表示这堆方块的层数和列数。

接下来输入  行，每行有一个长度为  的字符串，其中第  行的第  个字符表示位于 () 的方块上的字符。

接下来一行输入一个整数 ，表示字符串个数。

接下来输入  行，每行有一个长度不小于  的字符串，表示题面中所说的  个字符串。

另外，输入还保证 ，所有方块上的字符互不相同，每个字符都是大小写字母或数字中的一个，且所有字符串的长度之和为 ，且每个方块上的字符恰好在  个字符串中出现一次。

输出描述:

输出一行一个整数，表示不同的消除序列的个数模  的余数。

示例1

输入

复制

4 3
cbr
Rlo
euw
dEn
3
Red
bluE
crown

输出

复制