Преобразование таблицы

Ваня занимается работой с большими данными. Его проект занимается обработкой гигантских таблиц статистических данных. Ваня отвечает за разработку модуля преобразования таблиц, который выполняет перестановку строк, столбцов и ячеек таблицы.

Модуль занимается обработкой таблицы, состоящей из h строк и w столбцов, строки пронумерованы сверху вниз от 0 до h - 1, столбцы пронумерованы слева направо от 0 до w - 1. Ячейка в i-й строке, j-м столбце таблицы обозначается как [i, j]. Исходно ячейка [i, j] содержит число i * w + j.

На рис. 1. приведен пример исходного заполнения таблицы для h = 3, w = 5.

Модуль преобразования таблиц может выполнять следующие три типа операций.

На рис. 2. показано, как выглядит приведенная выше таблица после выполнения последовательности операций «c 0 1», «r 0 1», «f 0 0 1 2».

После выполнения всех операций Ваня вычисляет контрольную сумму для таблицы: сумма по всем ячейкам [i, j] значений (v[ij] * 17^i * 19^j) mod (10^9 + 7). Здесь v[ij] означает значение в ячейке [i, j], а операция «mod» означает операцию взятия остатка. Например, контрольная сумма для таблицы из примера вычисляется следующим образом: (6 * 17^0 * 19^0 + 2 * 17^0 * 19^1 + ... + 14 * 17^2 * 19^4) mod (10^9 + 7) = 564 830 737.

Помогите Ване выполнить все операции и вычислить контрольную сумму таблицы, которая получится в итоге.

Поскольку входные данные для этой задачи слишком велики, чтобы задавать их непосредственно, для ввода вам потребуется процедура расширения массива. Эта процедура не имеет специфических особенностей, которые надо использовать в решении задачи, предполагаемое жюри решение этой задачи в явном виде генерирует все массивы и далее работает с ними так же, как если бы оно считало их из входных данных.

Опишем процедуру генерации массива длины n по массиву длины 2 ≤ k ≤ n. Пусть задан массив целых неотрицательных чисел A = (a[1], a[2], ..., a[k]). Массив целых чисел Ax = (ax[1], ax[2], ..., ax[n]) будем называть расширением массива A по модулю r до размера n, если его элементы вычисляются по следующим формулам.

• Если 1 ≤ i ≤ k, то ax[i] = a[i].

• Если k + 1 ≤ i ≤ n, то ax[i] = (10007 * ax[i-2] + 10009 * ax[i-1] + 87277) mod r.

Здесь как «mod» также обозначена операция взятия остатка по модулю r. Например, выполним расширение массива A = (1, 4, 3) до 5 элементов по модулю 13.

ax[1] = a[1] = 1.

ax[2] = a[2] = 4.

ax[3] = a[3] = 3.

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

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

Таким образом, Ax = (1, 4, 3, 6, 6).

Входные данные

Первая строка ввода содержит числа h, w, n - размеры таблицы и число преобразований, которые необходимо выполнить (1 ≤ h, w ≤ 5 000, 2 ≤ n ≤ 10^6).

Вторая строка содержит строку s длины n - последовательность типов преобразований, s[i] = «c» задает операцию обмена столбцов, s[i] = «r» - операцию обмена строк, s[i] = «f» - операцию обмена ячеек.

Следующие четыре строки задают массивы A, B, C, D, соответственно. Каждый массив задается числом k, 2 ≤ k ≤ n, k ≤ 1000, после чего следует k чисел - элементы массива. Элементы массивов A и C удовлетворяют ограничению 0 ≤ a[i], c[i] ≤ h - 1, элементы массивов B и D удовлетворяют ограничению 0 ≤ b[i], d[i] ≤ w - 1.

Пусть Ax является расширением массива A по модулю h до размера n, массив Bx является расширением массива B по модулю w до размера n, массив Cx является расширением массива C по модулю h до размера n и массив Dx является расширением массива D по модулю w до размера n.

Операции, которые требуется выполнить с таблицей, определяются следующим образом: тип i-й операции задается символом s[i], а параметры получаются из массивов Ax, Bx, Cx, Dx.

• Если s[i] = «c», то i-я операция «c Bx[i] Dx[i]»;

• Если s[i] = «r», то i-я операция «r Ax[i] Cx[i]»;

• Если s[i] = «f», то i-я операция «f Ax[i] Bx[i] Cx[i] Dx[i]»;

Выходные данные

Выведите одно число - контрольную сумму таблицы после выполнения всех преобразований.

Примеры