eolymp
bolt
Try our new interface for solving problems
Problems

Перья на голове шамана

Перья на голове шамана

Time limit 2 seconds
Memory limit 256 MiB

Шаман украшений Пауэокунятль носит на голове n перьев. В начале они пронумерованы числами от 1 до n. Каждое утро Пауэокунятль переставляет перья, неукоснительно соблюдая определённый ритуал, то есть применяя фиксированную перестановку.

В некоторые дни Пауэокунятль совершает подвиги, и тогда Премудрый Бурундук подробно описывает в своих сказаниях расположение перьев на голове Пауэокунятля.

Вычислите, сколько ритуалов (перестановок) подходят под полученные описания.

Input data

В первой строке входного файла содержаться два целых числа n и m (1n10000, 1m10) - количество перьев на голове Пауэокунятля и число подвигов, которые он совершил.

Каждая из следующих m строк содержит число d_i (1d_i10^9) и перестановку чисел от 1 до n. Эта запись означает, что в d_i-й день, то есть когда Пауэокунятль провёл свой утренний ритуал ровно d_i раз, перья на его голове распологались ровно так.

Output data

Вывести количество ритуалов, подходящих под данные описания, по модулю "десять сотен сотен сотен да ещё дюжина без трёх".

Examples

Input example #1
5 1
2 1 2 3 4 5
Output example #1
26