Arko and Special Permutations

bisnu_sarkar BSMRSTU Monthly Contest,...
Limits 1s, 512 MB

Arko is very fond of permutations. He can easily calculate the number of nn length permutations. (In which permutations there contained nn numbers from 1 to nn are called nn length permutations. (2,1,3,4)(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 nn length permutations where rr specific values will be in same order.

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

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

So there are totally 3 valid permutations when (3,2)(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 nn and rr (1n1051 \le n \le 10^5, 1rn1 \le r \le n).

Next line will contain rr distinct numbers aia_i (1ain1 \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 109+710^9 + 7.

Sample

InputOutput
3 2
3 2
3

Submit

Login to submit.

Contributors

Statistics

76% Solution Ratio
prodip_bsmrstuEarliest, Dec '20
dipubalaFastest, 0.0s
tuhin107494Lightest, 5.5 kB
ShafahidShortest, 264B
Toph uses cookies. By continuing you agree to our Cookie Policy.