Problem B. Bouncing particles ≡

Statement

Suppose there is a rectangular area divided into N × M square cells. Some of these cells have particles.

In one time step, each particle can either stay in place or move to any of its neighboring cells.

It is required to count the number of possible particle movements, such that after L steps, they all end up in the same cell.

Since the obtained number may be too large, the answer should be the remainder when dividing it by (2³² − 5).

Input format

At the beginning of the input data there is a triplet of numbers N, M и L.

Then, the number K is specified, followed by a set of 2 × K indices of the starting cells: X_i, Y_i.

It is assumed that cell indexing starts from zero.

Output format

The output data should contain the obtained number.

Constraints

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

Sample tests

10 10 2
2
4 5
5 4

256

10 10 2
2
2 3
7 6

0