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

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

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

Рис. 1. Пример исходного заполнения таблицы.

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

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

выполняется операция <<c 0 1>>

выполняется операция <<r 0 1>>

выполняется операция <<f 0 1 1 2>>

Рис. 2. Пример преобразования таблицы

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

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

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

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

• Если $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$.

Здесь как <<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 \times ax\[2] + 10009 \times ax\[3] + 87277) \bmod 13 = 157332 \bmod 13 = 6$.
•  $ax\[5] = (10007 \times ax\[3] + 10009 \times ax\[4] + 87277) \bmod 13 = 177352 \bmod 13 = 6$.

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

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

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

Следующие четыре строки задают массивы $A$, $B$, $C$, $D$, соответственно. Каждый массив задается числом $k$, $2 \le k \le n$, $k \le 1000$, после чего следует $k$ чисел --- элементы массива. Элементы массивов $A$ и $C$ удовлетворяют ограничению $0 \le a\[i], c\[i] \le h - 1$, элементы массивов $B$ и $D$ удовлетворяют ограничению $0 \le b\[i], d\[i] \le 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]$>>;

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