대구일과학고등학교

서진이가 재학 중인 대구일과학고등학교는 대구광역시 소재의 고등학교로 $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$)
• 입력으로 주어지는 모든 수는 정수이다.