z-permutations
Little Z got homework based on permutations. His teacher gave him an integer n and a set A = {a1, ..., aK} and asked him how many n-permuations (on the set {1, 2, ..., n}) are there, such that they have inversions exactly at the positions a1, ..., aK.
For a permutation p1, ..., pn we say that there is an inversion at the position i if pi > pi + 1.
InputThe first line of the standard input contains two space-separated integers n (2 <= n <= 40) and K (1 <= K <= 10, 1 <= K <= n - 1). Next line will contain K different integers, a1, ..., aK (1 <= a1 <= n - 1), given in ascending order.
OutputTo the standard output you should print an integer that represents how many different permutations are there that contain inversions exactly at the positions a1, ..., aK with modulo 7155517.
Input:
Output:
3 2
1 2Output:
1Explanation:
All permutations are 123, 132, 213, 231, 312 and 321. The only one that has inversion at the positions 1 and 2 is 321.
Input:
Output:
4 1
2Output:
5Explanation:
Resulting permutations are: 1324, 1423, 2314, 2413 and 3412.
Input:
Output:
7 1
6Output:
6Explanation:
Resulting permutations are: 2345671, 1345672, 1245673, 1235674, 1234675 and 1234576.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.