# Counting Greedily Increasing Supersequences

Given a permutation $A = (a_1,
a_2, \dots , a_ N)$ of the integers $1, 2, \dots , N$, we define the
*greedily increasing subsequence* (GIS) in the following
way.

Let $g_1 = a_1$. For every $i > 1$, let $g_ i$ be the leftmost integer in $A$ that is strictly larger than $g_{i-1}$. If for a given $i$ there is no such integer, we say that the GIS of the sequence is the sequence $(g_1, g_2, ..., g_{i - 1})$.

For example, consider the permutation $(2, 3, 1, 5, 4, 7, 6)$. First, we have $g_1 = 2$. The leftmost integer larger than $2$ is $3$, so $g_2 = 3$. The leftmost integer larger than $3$ is $5$ ($1$ is too small), so $g_3 = 5$. Finally, $g_4 = 7$. Thus, the GIS of $(2, 3, 1, 5, 4, 7, 6)$ is $(2, 3, 5, 7)$.

Given a sequence $G = (g_1, g_2, \dots , g_ L)$, how many permutations $A$ of the integers $1, 2, \dots , N$ have $G$ as its GIS?

## Input

The first line of input contains the integers $1 \le N \le 10^6$, the number of elements of the permutation $A$, and $1 \le L \le 10^6$, the length of the sequence $G$.

The next line contains $L$ positive integers between $1$ and $N$, the elements $g_1, \dots , g_ L$ of the sequence $G$.

## Output

Output a single integer: the number of $N$-element permutations having the given sequence as its GIS. Since this number may be large, output it modulo the prime number $10^9 + 7$.

Sample Input 1 | Sample Output 1 |
---|---|

5 1 1 |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

5 1 5 |
24 |

Sample Input 3 | Sample Output 3 |
---|---|

5 3 2 4 5 |
8 |

Sample Input 4 | Sample Output 4 |
---|---|

7 4 1 4 5 7 |
20 |