ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1746. Гиперладья

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Точка n-мерного пространства называется допустимой, если все её координаты целые и лежат в отрезке от 0 до m − 1. Таким образом, существует mn различных допустимых точек. Гиперладья может сделать ход из допустимой точки a в допустимую точку b, если a и b различаются ровно в одной координате. Например, (0,2,1) → (2,2,1) → (2,2,0) → (2,1,0) является последовательностью из трёх ходов в трёхмерном пространстве.
Маршрут длины d из точки t0 в точку td — это последовательность допустимых точек t0, t1, …, td, такая что для любого i из множества {0, 1, …, d − 1} гиперладья может сделать ход из точки ti в точку ti + 1.
Даны целые числа n, m, d, q и допустимые точки t1, t2, …, tq. Требуется вычислить количество различных маршрутов длины d из ti в tj для всех пар (ij), где 1 ≤ i, jq.

Исходные данные

В первой строке через пробел записаны пять целых чисел n (1 ≤ n ≤ 50), m (2 ≤ m ≤ 105), d (0 ≤ d ≤ 109), p (1 ≤ p ≤ 109) и q (2 ≤ q ≤ 50). В следующих q строках записаны координаты точек ti.

Результат

Выведите q строк, по q чисел в каждой. j-е число в i-й строке должно быть равно количеству различных маршрутов длины d из ti в tj по модулю p.

Примеры

исходные данныерезультат
2 8 4 10000000 4
3 5
0 5
3 7
0 0
896 720 720 560
720 896 560 720
720 560 896 560
560 720 560 896
3 3 4 10000000 3
0 2 2
1 1 1
1 2 2
90 36 45
36 90 54
45 54 90
Автор задачи: Пётр Лежанкин
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009