Table Transformation

Vanya is working on a big data project that involves processing large statistical tables. His task is to develop a module that can transform these tables by rearranging their rows, columns, and cells.

The table has h rows and w columns, with rows numbered from 0 to h - 1 and columns from 0 to w - 1. Each cell at position [i, j] initially contains the value i * w + j.

In Figure 1, you can see an example of how the table is initially filled for h = 3 and w = 5.

The transformation module can perform three types of operations:

Figure 2 shows the table after executing the operations "c 0 1", "r 0 1", and "f 0 0 1 2".

After all operations, Vanya calculates the checksum of the table. This is the sum of all cell values [i, j] multiplied by (17^i * 19^j) modulo (10^9 + 7). Here, v[ij] is the value in cell [i, j], and "mod" refers to the remainder operation. For example, the checksum for the table in the example is calculated as: (6 * 17^0 * 19^0 + 2 * 17^0 * 19^1 + ... + 14 * 17^2 * 19^4) mod (10^9 + 7) = 564,830,737.

Your task is to help Vanya perform all operations and compute the checksum of the resulting table.

Due to the large input size, you will need to use an array expansion procedure. This procedure is not essential for solving the task; the intended solution generates all arrays and processes them as if they were read from the input.

Here's how to generate an array of length n from an array of length 2 ≤ k ≤ n. Given an array of non-negative integers A = (a[1], a[2], ..., a[k]), the extended array Ax = (ax[1], ax[2], ..., ax[n]) is created using the following rules:

• For 1 ≤ i ≤ k, ax[i] = a[i].

• For k + 1 ≤ i ≤ n, ax[i] = (10007 * ax[i-2] + 10009 * ax[i-1] + 87277) mod r.

Here, "mod" denotes the remainder operation modulo r. For example, extending the array A = (1, 4, 3) to 5 elements modulo 13 results in:

ax[1] = 1.

ax[2] = 4.

ax[3] = 3.

ax[4] = (10007 * ax[2] + 10009 * ax[3] + 87277) mod 13 = 157,332 mod 13 = 6.

ax[5] = (10007 * ax[3] + 10009 * ax[4] + 87277) mod 13 = 177,352 mod 13 = 6.

Thus, Ax = (1, 4, 3, 6, 6).

Input

The first line contains the numbers h, w, n - the table dimensions and the number of transformations (1 ≤ h, w ≤ 5,000, 2 ≤ n ≤ 10^6).

The second line contains the string s of length n, indicating the sequence of transformation types: s[i] = "c" for column swap, s[i] = "r" for row swap, and s[i] = "f" for cell swap.

The next four lines specify arrays A, B, C, D. Each array starts with the number k, 2 ≤ k ≤ n, k ≤ 1,000, followed by k numbers. Elements of A and C satisfy 0 ≤ a[i], c[i] ≤ h - 1, and elements of B and D satisfy 0 ≤ b[i], d[i] ≤ w - 1.

Let Ax be the extension of A modulo h to size n, Bx be the extension of B modulo w to size n, Cx be the extension of C modulo h to size n, and Dx be the extension of D modulo w to size n.

The operations are determined as follows: the type of the i-th operation is given by s[i], and the parameters are from Ax, Bx, Cx, Dx.

• If s[i] = "c", the operation is "c Bx[i] Dx[i]";

• If s[i] = "r", the operation is "r Ax[i] Cx[i]";

• If s[i] = "f", the operation is "f Ax[i] Bx[i] Cx[i] Dx[i]";

Output

Output a single number: the checksum of the table after all transformations.

Examples