题目描述

有一个 $h\times w$ 的表格，行编号为 $0$ 到 $h-1$，列编号为 $0$ 到 $w-1$。初始时，单元格 $[i,j]$ 中的数为：

$$i\times w+j.$$

需要执行 $n$ 次操作，操作有三类：

操作	形式	含义
交换列	c x y	交换第 $x$ 列和第 $y$ 列的内容
交换行	r x y	交换第 $x$ 行和第 $y$ 行的内容
交换单元格	f a b c d	交换单元格 $[a,b]$ 与 $[c,d]$ 的内容

执行完所有操作后，计算表格校验和：

$$\sum_{i,j} v[i][j]\times 17^i\times 19^j \bmod (10^9+7),$$

其中 $v[i][j]$ 为最终表格中单元格 $[i,j]$ 的值。

由于输入过大，操作参数通过数组扩展生成。

数组扩展规则

给定长度为 $k$ 的非负整数数组 $A=(a[1],a[2],\ldots,a[k])$，其中 $2\le k\le n$。它按模 $r$ 扩展到长度 $n$ 后得到数组 $Ax$：

• 若 $1\le i\le k$，则 $ax[i]=a[i]$；
• 若 $k+1\le i\le n$，则

$$ax[i]=(10007\times ax[i-2]+10009\times ax[i-1]+87277)\bmod r.$$

输入格式

第一行包含三个整数 $h,w,n$。

第二行包含长度为 $n$ 的字符串 $s$，表示每次操作类型：

• c 表示交换列；
• r 表示交换行；
• f 表示交换单元格。

接下来四行分别描述数组 $A,B,C,D$。每行格式为：先给出 $k$，再给出 $k$ 个整数。

约束：

• $1\le h,w\le 5000$；
• $2\le n\le 10^6$；
• $2\le k\le n$；
• $k\le 1000$；
• $A,C$ 的元素范围为 $[0,h-1]$；
• $B,D$ 的元素范围为 $[0,w-1]$。

令 $Ax,Bx,Cx,Dx$ 分别为四个数组按对应模数扩展到长度 $n$ 的结果。第 $i$ 次操作由 $s[i]$ 和这些数组确定：

• 若 $s[i]=\texttt{c}$，操作为 c Bx[i] Dx[i]；
• 若 $s[i]=\texttt{r}$，操作为 r Ax[i] Cx[i]；
• 若 $s[i]=\texttt{f}$，操作为 f Ax[i] Bx[i] Cx[i] Dx[i]。

输出格式

输出一个整数：所有操作执行完后的校验和。

样例输入

3 5 3
crf
3 0 0 0
3 0 0 1
3 0 1 1
3 1 0 2

样例输出

564830737

示意图

初始 $3\times5$ 表格如下。

依次执行 c 0 1、r 0 1、f 0 1 1 2 后，表格变化如下。