Arko and Special Permutations

Arko is very fond of permutations. He can easily calculate the number of $n$ length permutations. (In which permutations there contained $n$ numbers from 1 to $n$ are called $n$ length permutations. $(2, 1, 3, 4)$ is called a 4 length permutations.). So his teacher give him a tricky problem on permutations. He has to calculate the number of $n$ length permutations where $r$ specific values will be in same order.

There are total 6 permutations of 3 length. If two specific number $(3, 2)$ in the same order the valid permutations will be:

* $(1, 3, 2)$
* $(3, 1, 2)$
* $(3, 2, 1)$

So there are totally 3 valid permutations when $(3, 2)$ in the same order in 3 length permutations.

Arko didn’t able to solve this problem. Can you help him?

Input

The first line will contain two numbers $n$ and $r$ ($1 \le n \le 10^5$, $1 \le r \le n$).

Next line will contain $r$ distinct numbers $a_i$ ($1 \le a_i \le n$).

Output

You have to print the number of valid permutations. The answer can be very large. So you have to print the answer mod $10^9 + 7$.

Sample

Input	Output
3 2 3 2	3