Вычислить количество расположений чисел в строке, которые можно получить из начальной строки

Числообменник

Условие Числа от 1 до N выписаны подряд в строку. Разрешается менять местами любые два числа, между которыми в строке стоят ровно P1, P2, ... или PM, чисел (числа P1, P2, ..., PM заданы). Например, пусть N = 5, M = 2, P1 = 3, P2 = 2. Тогда после перестановки чиселв позициях 1 и 4 (между ними стоят 2 числа) и чисел в позициях 1 и 5 (между ними стоят 3 числа) получится по-следовательность 5, 2, 3, 1, 4. Напишите программу, вычисляющую количество расположений чисел в строке, которые можно получить из начальной строки какой либо последовательностью перестановок.

Формат входного файла Файлисходных данных INPUT.TXT содержит (в указанном порядке): N, M, P1, P2, ..., PM. Все числав файле разделяются пробелами и (или) символами переводастроки. Входные данные корректны.

Формат выходного файла В выходном файле OUTPUT.TXT должно находиться искомое число. Частичные решения задачи (количество перестановок < 2147 483 648) будут оцениваться исходя из 15 баллов. Естественно, в тестирующей системе частичные решения оцениваться не будут.

Ограничения 2≤ N ≤ 3000 1≤ M ≤ 500 Для всех i (1 ≤ i ≤ M) выполняется 0 ≤ P i ≤ N - 2

Примеры тестов

№ Входной файл (input.txt)
5
2
3 2
Выходной файл
24

0