문제 보기 - 힘 센 거북 (IZhO11_turtle)

언어	컴파일 명령
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o turtle turtle.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o turtle turtle.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o turtle turtle.cpp
Java	/usr/bin/javac -encoding UTF-8 turtle.java /bin/sh -c echo "Main-Class: turtle" > __manifest__.txt /bin/sh -c jar cfm turtle.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b turtle.py /bin/mv turtle.pyc __main__.pyc /usr/bin/zip turtle.pyz.zip __main__.pyc /bin/mv turtle.pyz.zip turtle.pyz

시간 제한	메모리 제한	제출 횟수	제출한 사람 수	해결한 사람 수	정답률
2000 ms	256 MiB	350	56	24	42.86%

$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)$ 에는 함정이 없음이 보장됩니다.

출력 형식

답을 출력합니다.

예제

예제 1

입력

1 1 1 0 1000
0 1

출력

예제 2

입력

2 2 0 0 10

출력

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

문제 출처

IZhO 2011 Day 1 C번