Задача 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 баллов. Естественно, в тестирующей системе частичные решения оцениваться не будут.

Ограничения

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

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

0.057s 0.009s 13