Зиад хочет совершить в Египте 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.
| Codeforces Beta Round 83 (Div. 1 Only) |
|---|
| Закончено |
