Перетворення таблиці

Ваня займається обробкою великих даних і працює над проєктом, що включає маніпуляції з великими таблицями статистичних даних. Його завдання полягає в розробці модуля для перетворення таблиць, який здатний змінювати порядок рядків, стовпців і комірок.

Таблиця, з якою працює Ваня, має 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]»;

Вихідні дані

Виведіть одне число — контрольну суму таблиці після виконання всіх перетворень.

Приклади