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