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