Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Arko and Special permutations

By bisnu_sarkar · Limits 1s, 512 MB

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(1n105, 1rn).

Next line will contain r distinct numbers ai (1ain)

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 + 7).

Sample

InputOutput
3 2
3 2
3

    Discussion

    Statistics


    65% Solution Ratio

    prodip_bsmrstuEarliest, 1M ago

    dipubalaFastest, 0.0s

    rabbycseLightest, 131 kB

    steinumShortest, 274B

    Submit

    Login to submit