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

Модуль занимается обработкой таблицы, состоящей из 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] значений (vij * 17i * 19j) mod (109 + 7). Здесь vij означает значение в ячейке [i, j], а операция «mod» означает операцию взятия остатка. Например, контрольная сумма для таблицы из примера вычисляется следующим образом: (6 * 170 * 190 + 2 * 170 * 191 + ... + 14 * 172 * 194) mod (109 + 7) = 564 830 737.

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

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

Опишем процедуру генерации массива длины n по массиву длины 2 ≤ k ≤ n. Пусть задан массив целых неотрицательных чисел A = (a1, a2, ..., ak). Массив целых чисел Ax = (ax1, ax2, ..., axn) будем называть расширением массива A по модулю r до размера n, если его элементы вычисляются по следующим формулам.

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

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

ax1 = a1 = 1.

ax2 = a2 = 4.

ax3 = a3 = 3.

ax4 = (10007 * ax2 + 10009 * ax3 + 87277) mod 13 = 157332 mod 13 = 6.

ax5 = (10007 * ax3 + 10009 * ax4 + 87277) mod 13 = 177352 mod 13 = 6.

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

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

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

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

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

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

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

• Если si = «c», то i-я операция «cBxi Dxi»;
• Если si = «r», то i-я операция «rAxi Cxi»;
• Если si = «f», то i-я операция «fAxi Bxi Cxi Dxi»;

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

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