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

서진이의 위치가 $ (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>

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

출력 형식

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

예제 입력

4 2 1
2 3

예제 출력

9