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 ->
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?
The first line will contain two numbers n and r(1 ≤ n ≤ 105, 1 ≤ r ≤ n).
Next line will contain r distinct numbers ai (1 ≤ ai ≤ n)
You have to print the number of valid permutations. The answer can be very large. So you have to print the answer MOD (109 + 7).
3 2 3 2