탐욕 증가 수열을 갖는 순열의 개수 세기

정수 $1, 2, \dots, N$의 순열 $A = (a_1, a_2, \dots, a_N)$이 주어질 때, 탐욕 증가 부분수열(GIS)을 다음과 같이 정의한다.

$g_1 = a_1$이라 하자. 각 $i > 1$에 대해, $g_i$는 $A$에서 $g_{i-1}$보다 엄격히 큰 가장 왼쪽의 정수이다. 주어진 $i$에 대해 그러한 정수가 존재하지 않으면, 수열의 GIS는 $(g_1, g_2, ..., g_{i - 1})$이라 한다.

예를 들어 순열 $(2, 3, 1, 5, 4, 7, 6)$을 생각하자. 먼저 $g_1 = 2$이다. $2$보다 큰 가장 왼쪽의 정수는 $3$이므로 $g_2 = 3$이다. $3$보다 큰 가장 왼쪽의 정수는 $5$이다($1$은 너무 작다). 따라서 $g_3 = 5$이다. 마지막으로 $g_4 = 7$이다. 그러므로 $(2, 3, 1, 5, 4, 7, 6)$의 GIS는 $(2, 3, 5, 7)$이다.

수열 $G = (g_1, g_2, \dots, g_L)$이 주어질 때, GIS가 $G$인 정수 $1, 2, \dots, N$의 순열 $A$는 몇 개인가?

첫째 줄에 순열 $A$의 원소 개수 $1 \le N \le 10^6$과 수열 $G$의 길이 $1 \le L \le 10^6$이 주어진다.

다음 줄에 $1$과 $N$ 사이의 $L$개의 양의 정수 $g_1, \dots, g_L$이 주어진다.

주어진 수열을 GIS로 갖는 $N$개 원소 순열의 개수를 하나의 정수로 출력한다. 이 수는 클 수 있으므로 소수 $10^9 + 7$로 나눈 나머지를 출력한다.