원점에서 실제로 보이는 점

$N$차원 좌표계에 점이 여러 개 놓여 있다. 이 점들은 $M$개의 자연수 $X_1, X_2, \dots, X_M$으로 나타내며, $X_i$가 나타내는 점의 집합 $S_i$는 다음과 같다.

$S_i = \{(x_1, x_2, \dots, x_N) \mid 1 \le x_1 \le x_2 \le \dots \le x_N = X_i\}$

여기서 $x_1, x_2, \dots, x_N$은 모두 자연수다.

모든 $S_i$를 합한 집합을 $S = S_1 \cup S_2 \cup \dots \cup S_M$이라고 하자. 좌표계에 놓인 점은 $S$에 속한 점이 전부다.

원점 $(0, 0, \dots, 0)$에서 보이는 점이 몇 개인지 구하라. 점 $p$가 보인다는 것은 원점과 $p$를 잇는 선분 위에 $p$ 자신을 뺀 $S$의 점이 하나도 없다는 뜻이다. 선분 위에 있어도 $S$에 속하지 않는 좌표는 시야를 가리지 않는다.

첫째 줄에 자연수 $N$과 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 100000$, $1 \le M \le 100000$)

둘째 줄부터 $M$개 줄에 걸쳐 자연수 $X_i$가 한 줄에 하나씩 주어진다. ($1 \le X_i \le 100000$) $X_i$는 서로 다르다.

원점에서 보이는 점의 개수를 $1000000007$로 나눈 나머지를 출력한다.

$N = 2$이고 $X$가 1, 2, 3, 4일 때 $S$의 점은 $(1,1)$, $(1,2)$, $(2,2)$, $(1,3)$, $(2,3)$, $(3,3)$, $(1,4)$, $(2,4)$, $(3,4)$, $(4,4)$이다. 이 가운데 보이는 점은 $(1,1)$, $(1,2)$, $(1,3)$, $(2,3)$, $(1,4)$, $(3,4)$로 모두 6개다. $(4,4)$는 선분 위의 $(3,3)$이 $S$에 있어서 가려지고, $(2,4)$는 $(1,2)$에 가려진다.

$X$가 4 하나뿐이면 결과가 달라진다. $S$는 $(1,4)$, $(2,4)$, $(3,4)$, $(4,4)$뿐이고 $(2,4)$를 가릴 $(1,2)$가 $S$에 없으므로 네 점이 모두 보인다.