Зиад хочет совершить в Египте n преступлений и остаться безнаказанным. Законодательство Египта предусматривает различные статьи за различные типы преступлений. К примеру, взяточничество является преступлением, но оно перестает быть таковым, если оно повторено дважды. Соответственно, взяточничество не считается преступлением, если оно было совершено четное количество раз. Превышение скорости тоже является преступлением, но оно перестает быть таковым, будучи повторенным кратное пяти количество раз.
В случае Египта известно c условий, налагаемых на повторяемость преступлений. Каждое ограничение представляет собой тип преступления ti и его разрешенную кратность mi. Если количество раз, которое Зиад совершил преступление типа ti кратно mi, то он не будет наказан за преступления этого типа. Некоторые типы преступлений могут быть перечислены более одного раза. В этом случае достаточно удовлетворить одному из ограничений для этого типа преступления, чтобы не быть наказанным за него. Естественно, если Зиад не совершил ни одного преступления некоторого типа, то он не будет наказан за преступления этого типа.
Обладая вышеприведенной информацией, Зиад интересуется, сколькими способами можно совершить в Египте ровно n преступлений и остаться безнаказанным?
Порядок совершения преступлений имеет значение. Более формально, два способа, последовательности w1 и w2, считаются одинаковыми, если w1i = w2i, для любого 1 ≤ i ≤ n.
Выходные данные
Выведите количество способов совершить ровно n преступлений, по модулю 12345.
Примечание
В первом примере возможны следующие 16 способов: AAAAA, AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA, ABBBB, BABBB, BBABB, BBBAB, BBBBA.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
A 1
B 2
|
16
|
|
2
|
6 3
A 1
B 2
C 3
|
113
|
|
3
|
8 3
A 2
A 3
B 2
|
128
|