D. Преступление и наказание
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Зиад хочет совершить в Египте n преступлений и остаться безнаказанным. Законодательство Египта предусматривает различные статьи за различные типы преступлений. К примеру, взяточничество является преступлением, но оно перестает быть таковым, если оно повторено дважды. Соответственно, взяточничество не считается преступлением, если оно было совершено четное количество раз. Превышение скорости тоже является преступлением, но оно перестает быть таковым, будучи повторенным кратное пяти количество раз.

В случае Египта известно c условий, налагаемых на повторяемость преступлений. Каждое ограничение представляет собой тип преступления ti и его разрешенную кратность mi. Если количество раз, которое Зиад совершил преступление типа ti кратно mi, то он не будет наказан за преступления этого типа. Некоторые типы преступлений могут быть перечислены более одного раза. В этом случае достаточно удовлетворить одному из ограничений для этого типа преступления, чтобы не быть наказанным за него. Естественно, если Зиад не совершил ни одного преступления некоторого типа, то он не будет наказан за преступления этого типа.

Обладая вышеприведенной информацией, Зиад интересуется, сколькими способами можно совершить в Египте ровно n преступлений и остаться безнаказанным?

Порядок совершения преступлений имеет значение. Более формально, два способа, последовательности w1 и w2, считаются одинаковыми, если w1i = w2i, для любого 1 ≤ i ≤ n.

Входные данные

На первой строке записано два целых числа n и c (0 ≤ n ≤ 1018, 0 ≤ c ≤ 1000) — суммарное количество преступлений, которые хочет совершить Зиад, и количество ограничений на кратность преступлений.

Затем следуют описания c ограничений на кратность. Всего существует 26 типов преступлений. Каждое ограничение задается типом преступления — большой латинской буквой — и его кратностью.

Все кратности являются целыми положительными числами, и произведение всех кратностей во входных данных не превосходит 123. Некоторые ограничения на кратность могут повторяться во входных данных более одного раза.

Если кратность какого-то преступления равна 1, то, независимо от того, сколько раз это преступление было совершено, наказания за него не последует. Строгость египетских законов компенсируется необязательностью их выполнения.

Конечно, если какой-то тип преступлений не перечислен в списке ограничений на кратности, Зиад не собирается совершать преступления этого типа, ибо наказание за них последует неминуемо.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).

Выходные данные

Выведите количество способов совершить ровно n преступлений, по модулю 12345.

Примеры
Входные данные
5 2
A 1
B 2
Выходные данные
16
Входные данные
6 3
A 1
B 2
C 3
Выходные данные
113
Входные данные
8 3
A 2
A 3
B 2
Выходные данные
128
Примечание

В первом примере возможны следующие 16 способов: AAAAA, AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA, ABBBB, BABBB, BBABB, BBBAB, BBBBA.