ICPC 2019 test tour - Числообменник

Задача C. Числообменник ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	IX Всероссийская олимпиада школьников	Ограничение времени:	5 сек
Входной файл:	input.txt	Ограничение памяти:	200 Мб
Выходной файл:	output.txt

Условие

Числа от 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 должно находиться искомое число.

Частичные решения задачи (количество перестановок < 2 147 483 648) будут оцениваться исходя из 15 баллов. Естественно, в тестирующей системе частичные решения оцениваться не будут.

Ограничения

2 ≤ N ≤ 3000
1 ≤ M ≤ 500
Для всех i (1 ≤ i ≤ M) выполняется 0 ≤ P_i ≤ N - 2

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

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