Перья на голове шамана
Шаман украшений Пауэокунятль носит на голове n перьев. В начале они пронумерованы числами от 1 до n. Каждое утро Пауэокунятль переставляет перья, неукоснительно соблюдая определённый ритуал, то есть применяя фиксированную перестановку.
В некоторые дни Пауэокунятль совершает подвиги, и тогда Премудрый Бурундук подробно описывает в своих сказаниях расположение перьев на голове Пауэокунятля.
Вычислите, сколько ритуалов (перестановок) подходят под полученные описания.
Входные данные
В первой строке входного файла содержаться два целых числа n и m (1 ≤ n ≤ 10000, 1 ≤ m ≤ 10) - количество перьев на голове Пауэокунятля и число подвигов, которые он совершил.
Каждая из следующих m строк содержит число d_i (1 ≤ d_i ≤ 10^9) и перестановку чисел от 1 до n. Эта запись означает, что в d_i-й день, то есть когда Пауэокунятль провёл свой утренний ритуал ровно d_i раз, перья на его голове распологались ровно так.
Выходные данные
Вывести количество ритуалов, подходящих под данные описания, по модулю "десять сотен сотен сотен да ещё дюжина без трёх".