Daegu Ilgwa Science High School

Daegu Ilgwa Science High School is a high school in Daegu Metropolitan City, located in $d$-dimensional space. Graduating seniors must move out of their dormitories after the college entrance exam and commute to school. Seojin is a third-year student, so Seojin is worried about the commute and decided to look for a route. The walk from Seojin's home to the school must follow a special rule.

If Seojin is at $(p_1, p_2, \ldots, p_{d-1}, p_d)$, Seojin can move to one of these positions: $(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)$. On the way from home to school, Seojin found $P$ points that must be passed. These points must be passed in the given order. No point is repeated, and no point is at the same position as Seojin's home or the school.

Seojin's home is at $(a_1, a_2, \ldots, a_{d-1}, a_d)$, and the school is at $(b_1, b_2, \ldots, b_{d-1}, b_d)$. Here, $a_i = 1$ and $b_i = N$ for every $1 \le i \le d$. Find the number of ways to move from home to the school, modulo $10^9+7$.

The first line contains $N$, $d$, and $P$, separated by spaces. From the second line on, the $P$ lines each contain the coordinates of a point, $q_{i,1}, q_{i,2}, \ldots, q_{i,d-1}, q_{i,d}$, separated by spaces.

Print the answer on the first line.

• $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$)
• All numbers in the input are integers.