대구일과학고등학교

대구일과학고등학교는 대구광역시에 있는 고등학교로, $d$차원 공간에 위치한다. 졸업 예정자들은 수능이 끝나면 기숙사에서 방을 빼고 통학해야 한다. 서진이는 현재 3학년이라 곧 통학하게 될 처지를 걱정하며 등굣길을 찾아보기로 했다. 서진이의 집에서 학교까지 갈 때는 특별한 규칙을 따라야 한다.

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

서진이의 집은 $(a_1, a_2, \ldots, a_{d-1}, a_d)$에, 학교는 $(b_1, b_2, \ldots, 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}, \ldots, 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$)
• 입력으로 주어지는 모든 수는 정수이다.