A permutation of size n is an ordered set of n numbers in which each number from 1 to n occurs exactly once. For example, (4, 2, 3, 5, 1) is a permutation of size 5.
We are given a number n and a sequence a, in which there are k natural numbers.
Calculate how many permutations of size n exist that do not start with the given sequence.
Input data format
The first line contains two positive integers n and k (1 <= n <= 9, 1 <= k <= 100) .
The second line contains k natural numbers, constituting the sequence a. Each of these numbers does not exceed 100.
Output format
Print the number of permutations of size n- that do not start with the given sequence a.
|
Enter |
Output |
3 2
2 1
|
5 |
5 2
4 4 |
120
|
5 6
2 3 9 5 6 6
|
120
|