Good Game

시간 제한2초메모리 제한512 MB

요약

n차원에서 원점부터 목표점까지 좌표가 비감소하는 경로 중 m개의 장애물을 지나지 않는 경로의 수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 9점
유형: 조합론, 동적 계획법, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

$n$ 차원 공간에서 $(0, 0, \ldots, 0)$ 에서 $(a_0, a_1, \ldots, a_{n - 1})$ 까지 걷고자 한다. 각 걸음마다 좌표 벡터의 성분 하나를 1만큼 증가시킬 수 있다. $m$ 개의 장애물 $p_1, p_2, \ldots, p_m$ 이 있다. 장애물을 지나지 않는 경로의 수를 구하라.

그러나 이 문제는 8102년의 ICPC 대회에 내기에는 너무 쉽다. 조건을 하나 더 추가한다. 경로 위의 모든 점 $(x_0, x_1, \ldots, x_{n - 1})$ 에 대해 이 벡터의 성분은 감소하지 않아야 한다: $x_0 \leq x_1 \leq \ldots \leq x_{n - 1}$ .

경로의 수를 $10^9 + 7$ 로 나눈 나머지를 출력하라.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \leq n \leq 50$ , $0 \leq m \leq 50$ ).

둘째 줄에 $n$ 개의 정수 $a_0, a_1, \ldots, a_{n-1}$ 이 주어진다 ( $0 \leq a_0 \leq a_1 \leq \ldots \leq a_{n-1} \leq 10^4$ ). 이는 도착점의 좌표 벡터이다.

다음 $m$ 개의 줄에 장애물이 주어진다. 이 중 $i$ 번째 줄에는 $n$ 개의 정수 $p_{i, 0}, p_{i, 1}, \ldots, p_{i, n - 1}$ 이 주어진다 ( $0 \leq p_{i, 0} \leq p_{i, 1} \leq \ldots \leq p_{i, n - 1} \leq 10^4$ ). 이는 장애물의 좌표 벡터이다.

시작점, 도착점, 모든 장애물은 서로 다르다.

출력

답을 $10^9 + 7$ 로 나눈 나머지를 출력하라.

예제2

예제 1
입력
```
2 0
3 3
```
예상 출력
```
5
```
예제 2
입력
```
4 2
1 2 3 4
0 1 2 3
1 1 2 2
```
예상 출력
```
312
```