Перестановкой размера n называется упорядоченный набор из n чисел, в котором каждое число от 1 до n встречается ровно один раз. Например, (4, 2, 3, 5, 1) - это перестановка размера 5.
Нам дано число n и последовательность a, в которой k натуральных чисел.
Вычислите, сколько существует перестановок размера n, которые не начинаются на данную последовательность.
Формат входных данных
В первой строке содержатся два натуральных числа n и k (1 <= n <= 9, 1 <= k <= 100) .
Во второй строке содержатся k натуральных чисел, составляющие последовательность a. Каждое из этих чисел не превышает 100.
Формат выходных данных
Выведите количество перестановок размера n- которые не начинаются на данную последовательность a.
| Ввод |
Вывод |
3 2
2 1 |
5 |
5 2
4 4 |
120 |
5 6
2 3 9 5 6 6 |
120 |