11832번 - Energetic turtle 다국어

There is a grid with N + 1 rows and M + 1 columns. The turtle, which is on the cell (0, 0), wants to get into the cell (N, M). The turtle can only go up or right. There are K traps on the grid. If the turtle will get to one of these traps, it will turn up. The turtle has strength to stand up no more than T times. Calculate, how many different ways the turtle can reach the cell (N, M). Since this number can be very large, output the remainder of his division by Z.

The first line contains 5 integers N, M, K, T and Z (1 ≤ N, M ≤ 300000, 0 ≤ K, T ≤ 20, 1 ≤ Z ≤ 1000000000). Each of the following K lines contains coordinates of a cell with a trap: X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). It’s guaranteed that all traps situated in different cells and there is no trap in cells (0, 0) and (N, M).

Print one number – the answer.