표 변환

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

Модуль занимается обработкой таблицы, состоящей из $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$.

Здесь как <> также обозначена операция взятия остатка по модулю $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]$>>;

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