题目背景

周末，学校棋社正在筹备一场“幻想棋子”展示活动。棋社成员林遥设计了一种名为独角兽的新棋子：它的跳跃方式与国际象棋中的马有些相似，但每次都要跳得更远。

为了测试这种棋子的行动规律，林遥让程序随机生成一张字母棋盘，并给出一个目标单词。她想知道，独角兽一共有多少种不同的跳跃路线可以依次经过这些字母。

题目描述

有一张包含 $R$ 行、$C$ 列的棋盘。每个格子中都有一个大写英文字母，且所有字母均来自字母表中的前 $L$ 个字母。

棋盘中的字母由下文给出的伪随机过程生成。

设独角兽当前位于格子 $(r_1,c_1)$，准备跳到格子 $(r_2,c_2)$。一次跳跃合法，当且仅当满足下面两个条件之一：

$$|r_1-r_2|\ge 3\quad\text{且}\quad |c_1-c_2|\ge 2,$$

或

$$|r_1-r_2|\ge 2\quad\text{且}\quad |c_1-c_2|\ge 3.$$

也就是说，独角兽需要沿一个基本方向移动至少 $3$ 格，再沿与之垂直的方向移动至少 $2$ 格；两个方向的先后顺序可以交换。

现在给定一个字符串 word。你需要：

1. 将独角兽放在一个字母等于 word 第一个字符的格子上；
2. 每次进行一次合法跳跃，并落在字母等于 word 下一个字符的格子上；
3. 依次经过 word 的全部字符。

不同的格子序列被视为不同的方案。路线中允许多次经过同一个格子。

请计算合法方案数，并对 $1\,000\,000\,007$ 取模。

棋盘生成方式

棋盘按照从上到下、从左到右的顺序生成。伪代码如下：

x = seed
d = (65535 div L) + 1

for r = 0 ... R - 1
    for c = 0 ... C - 1
        x = (x * 25173 + 13849) modulo 65536
        chessboard[r][c] = ASCII 码为 65 + (x div d) 的字符

其中，A div B 表示整数除法，即只保留 $A/B$ 的整数部分。

输入格式

第一行包含四个整数 $R,C,L,seed$。

第二行包含一个仅由大写英文字母组成的字符串 word。

输出格式

输出一个整数，表示独角兽依次经过 word 中全部字符的方案数，对 $1\,000\,000\,007$ 取模后的结果。

样例 1

输入

3 4 2 47
AB

输出

2

说明

生成的棋盘为：

ABBA
AAAA
BBBB

独角兽只能从第一行的两个角落出发，并跳到对侧的另一个角落，因此共有 $2$ 种方案。

样例 2

输入

5 5 2 47
CD

输出

0

说明

棋盘中不会出现字母 C，因此没有合法方案。

样例 3

输入

4 4 1 42
AA

输出

20

说明

棋盘中的所有格子均为 A。

独角兽可以从四个角落中的任意一个出发，每个角落有 $3$ 个合法落点；还可以从与角落共边的 $8$ 个格子出发，每个这样的格子有 $1$ 个合法落点。

因此答案为

$$4\times 3+8\times 1=20.$$

样例 4

输入

4 4 1 42
AAAAA

输出

172

样例 5

输入

1 1 5 54321
ABCDE

输出

0

说明

棋盘只有一个格子，无法完成任何跳跃，因此长度大于 $1$ 的单词一定无法被经过。

样例 6

输入

8 8 26 226
TOPCODER

输出

1

数据范围

• $1\le R\le 300$；
• $1\le C\le 300$；
• $1\le L\le 26$；
• $0\le seed\le 65535$；
• $1\le |word|\le 50$；
• word 中的每个字符都是大写英文字母 A 到 Z。