Given a grid with N + 1 rows and M + 1 columns. The turtle is on cell (0, 0) and wants to get to cell (N, M). The turtle can only go up or to the right. There are traps in K cells on the grid. If the turtle goes to one of these cages, it will roll over. The turtle has the strength to stand up no more than T times. Count how many different ways the turtle can get into the cage (N, M). Since this number can be very large, print the remainder after dividing it by Z.
Input
The first line of the input file contains 5 integers: N, M, K, T and Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T 20, 1 ≤ Z ≤ 10
9). Each of the next K lines contains the coordinates of the corresponding cell with the trap X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). It is guaranteed that all cells with traps are different and there are no traps in cells (0, 0) and (N, M).
Imprint
Output the desired number.
Examples
| # |
Input |
Output |
| 1 |
1 1 1 0 100
0 1
| 1 |
| 2 |
2 2 0 0 10 |
6 |