Шаман прикрас Пауеокунятль носить на голові \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 Вивести кількість ритуалів, які підходять під задані описи, по модулю "десять сотень сотень сотень да ще дюжина без трьох".