Задача B. Bouncing particles ≡

Условие

Пусть имеется прямоугольная область, разделенная N × M квадратных ячеек. В некоторых из указанных ячеек были размещены частицы.

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

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

Так как полученное число может оказаться слишком большим, в качестве ответа следует вывести остаток от его деления на (2³² − 5).

Формат входных данных

В начале входных данных записана тройка чисел N, M и L.

Далее указано число K, за которым следует набор из 2 × K индексов стартовых ячеек: X_i, Y_i.

Здесь полагается, что индексация ячеек начинается с нуля.

Формат выходных данных

Выходные данные должны содержать полученное число.

Ограничения

1 ≤ N ⋅ M ≤ 2 500, 0 ≤ L ≤ 50, 2 ≤ K ≤ 50, 0 ≤ X_i < N, 0 ≤ Y_i < M.

Примеры тестов

10 10 2
2
4 5
5 4

256

10 10 2
2
2 3
7 6

0