30398번 - 대구일과학고등학교

문제

서진이가 재학 중인 대구일과학고등학교는 대구광역시 소재의 고등학교로 $d$ 차원에 존재한다. 대구일과학고등학교의 졸업 예정자들은 수능이 끝난 후 기숙사에서 방을 빼고, 통학해야 한다. 서진이는 현재 3학년이기 때문에, 곧 통학해야 하는 자신의 처지를 걱정하며 등굣길을 찾아보기로 했다. 서진이의 집에서 대구일과학고등학교로 갈 때는 특별한 규칙을 따라야 한다.

서진이의 위치가 $ (p_1, p_2, ... , p_{d-1}, p_d) $라면, 서진이는 $(p_1 +1,p_2,...,p_{d-1},p_d),ドル $(p_1,p_2+1,...,p_{d-1},p_d),ドル ..., $(p_1,p_2,...,p_{d-1} + 1 ,p_d),ドル $(p_1,p_2,...,p_{d-1},p_d +1)$ 중 하나의 위치로 이동할 수 있다. 서진이는 집에서 대구일과학고로 갈 때 반드시 지나야 하는 $P$개의 점들을 발견했다. 이 점들은 반드시 순서대로 지나야 하며, 이 점들 중에 중복되는 점은 없으며, 서진이의 집이나 대구일과학고등학교와 같은 위치에 있는 점도 없다.

서진이의 집은 $(a_1,a_2,...,a_{d-1},a_d)$에 위치하고, 대구일과학고등학교는 $(b_1,b_2,...,b_{d-1},b_d)$에 위치한다.

이때, 모든 1ドル \le i \le d$ 에 대해 $ a_i = 1 ,ドル $ b_i = N $을 만족한다. 서진이의 집에서 대구일과학고등학교로 이동하는 경우의 수를 10ドル^9+7$로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 $ N, d $와 $P$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $P$개의 줄에 점의 좌표 $q_{i,1}, q_{i,2}, ..., q_{i,d-1}, q_{i,d}$ 가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 답을 출력한다.

제한

• 0ドル \le P\le 1000$
• $ 2 \le N$
• $ 1 \le d $
• $N \times d \le 10^6 $
• $d \times P \le 10^6 $
• $ 1 \le q_{i,j} \le N $ (1ドル \le i \le P,ドル $ 1 \le j \le d$)
• $ q_{i,j} \le q_{i+1,j} $ ($ 1 \le i<P,ドル $ 1 \le j \le d $)
• 입력으로 주어지는 모든 수는 정수이다.

노트