Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
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?
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).
Input | Output |
---|---|
3 2 3 2 | 3 |
65% Solution Ratio
prodip_bsmrstuEarliest,
dipubalaFastest, 0.0s
rabbycseLightest, 131 kB
steinumShortest, 274B
Login to submit