Олимпиадный тренинг

Задача . D. Раскраска крестиками


Задача

Темы: математика реализация Структуры данных *1700

Представьте лист бумаги — сетку размера \(n \times m\): \(n\) строк и \(m\) столбцов с ячейками. Все ячейки изначально белые.

К листу применили \(q\) операций. \(i\)-я из них может быть описана следующим образом:

  • \(x_i\) \(y_i\) — выбирается один из \(k\) небелых цветов, и вся строка \(x_i\) и весь столбец \(y_i\) раскрашиваются в этот цвет. Новый цвет наносится на каждую клетку вне зависимости от того, была ли клетка раскрашена до операции.

Лист после применения всех \(q\) операций называется раскраской. Две раскраски различные, если существует хотя бы одна клетка, раскрашенная в разные цвета.

Сколько существует различных раскрасок? Выведите их количество по модулю \(998\,244\,353\).

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

В первой строке записано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

В первой строке каждого набора записаны четыре целых числа \(n, m, k\) и \(q\) (\(1 \le n, m, k, q \le 2 \cdot 10^5\)) — размер листа, количество небелых цветов и количество операций.

В \(i\)-й из следующих \(q\) строк записана \(i\)-я операция — два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i \le n\); \(1 \le y_i \le m\)) — строка и столбец, к которым применяется операция.

Сумма \(q\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).

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

На каждый набор входных данных выведите одно целое число — количество различных раскрасок по модулю \(998\,244\,353\).


Примеры
№Входные данныеВыходные данные
1 2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2 
3
4

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет