Пір'їни на голові шамана#4335
Шаман прикрас Пауеокунятль носить на голові пір'їн. Спочатку вони пронумеровані числами від до . Кожного ранку Пауеокунятль переставляє пір'їни, неухильно дотримуючись певного ритуалу, тобто застосовуючи фіксовану перестановку.
У деякі дні Пауеокунятль здійснює подвиги, і тоді Премудрий Бурундук детально описує у своїх розповідях розміщення пір'їн на голові Пауеокунятля.
Обчисліть, скільки ритуалів (перестановок) підходить під отримані описи.
У першому рядку вхідного файлу містяться два цілих числа та (1 \leq n \leq 10000, 1 \leq m \leq 10) - кількість пір'їн на голові Пауеокунятля та число подвигів, які він здійснив.
Кожен з наступних рядків містить число d_i (1 \leq d_i \leq 10^9) та перестановку чисел від до . Цей запис означає, що у d_i-й день, тобто коли Пауеокунятль провів свій ранковий ритуал рівно d_i раз, пір'їни на його голові розміщувались саме так.
Виведіть кількість ритуалів, які підходять під задані описи, по модулю "десять сотень сотень сотень та ще дюжина без трьох".
Приклад 1