기운찬 거북이

$(N+1) \times (M+1)$ 크기의 격자가 있다. 행에는 $0$부터 $N$까지, 열에는 $0$부터 $M$까지 번호가 붙어 있고, $x$행 $y$열 칸을 $(x, y)$로 나타낸다. 거북이는 $(0, 0)$에서 출발해 $(N, M)$으로 가려고 한다. 거북이는 한 번에 $(x, y)$에서 $(x+1, y)$ 또는 $(x, y+1)$로만 이동한다.

격자에는 함정이 $K$개 있다. 함정이 있는 칸을 밟으면 거북이는 뒤집히고, 다시 일어나야 한다. 거북이가 일어날 힘은 최대 $T$번 분량이므로, 거북이가 지나갈 수 있는 경로에 있는 함정은 $T$개 이하다.

거북이가 $(0, 0)$에서 $(N, M)$까지 갈 수 있는 서로 다른 경로의 수를 구하여라. 이 수가 매우 클 수 있으므로 $Z$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $N$, $M$, $K$, $T$, $Z$가 주어진다 ($1 \le N, M \le 300000$, $0 \le K, T \le 20$, $1 \le Z \le 1000000000$).

다음 $K$개 줄에는 함정이 있는 칸의 좌표 $X$와 $Y$가 주어진다 ($0 \le X \le N$, $0 \le Y \le M$). 함정은 모두 서로 다른 칸에 있고, $(0, 0)$과 $(N, M)$에는 함정이 없다.

첫째 줄에 경로의 수를 $Z$로 나눈 나머지를 출력한다.