힘 센 거북 Batch 컴파일 명령

$N+1$행 $M+1$열 크기의 격자판이 있습니다. 격자 $(0, 0)$에 있는 거북은 격자 $(N, M)$로 가고 싶습니다. 거북은 북쪽 또는 동쪽으로만 이동할 수 있습니다. 격자판에는 $K$개의 함정이 있습니다. 거북이 함정이 있는 칸에 들어가면 뒤집힐 것입니다. 거북은 뒤집어진 상태에서 최대 $T$번까지 원래대로 몸을 돌릴 수 있습니다. 거북이 $(N, M)$에 도착할 수 있는 경우의 수를 계산하는 프로그램을 작성하세요. 이 숫자는 매우 클 수 있으므로, $Z$로 나눈 나머지를 출력하세요.

입력 형식

첫 번째 줄에 다섯 개의 정수 $N, M, K, T, Z$ ($1 \le N,M \le 300 000, 0 \le K,T \le 20, 1 \le Z \le 1 000 000 000$)가 주어집니다. 다음 $K$개 줄에는 함정이 있는 격자의 위치 $X, Y$ ($0 \le X \le N, 0 \le Y \le M$)이 주어집니다. 모든 함정은 서로 다른 격자에 묻혀 있으며 $(0, 0)$과 $(N, M)$에는 함정이 없음이 보장됩니다.

출력 형식

답을 출력합니다.

예제

40%의 데이터에 대해 $N, M \le 1000.$