CF107D Crime Management

Zeyad 想要在埃及犯下 $n$ 起罪行，并且不受惩罚。罪行有几种类型。例如，贿赂是一种罪行，但如果重复两次，它就不被视为犯罪。因此，贿赂在重复偶数次时不被视为犯罪。超速也是一种罪行，但如果其重复的次数是 5 的倍数，它也不被视为犯罪。 更具体地说，已知有 $c$ 条关于罪行重复的条件。每个条件描述了罪行的类型 $t_{i}$ 及其重复的次数限制 $m_{i}$ 。如果 Zeyad 犯下的罪行 $t_{i}$ 的次数是 $m_{i}$ 的倍数，则 Zeyad 不会因为该罪行而受到惩罚。如果某种罪行出现多次，满足其中任意一个条件即可不受惩罚。当然，如果某罪行的次数为零，Zeyad 对该罪行无罪。 现在，Zeyad 想知道有多少种方式可以精确犯下 $n$ 起罪行且不受惩罚。 罪行的顺序是重要的。更正式地说，犯下 $n$ 起罪行的两种方式（序列 $w1$ 和 $w2$ ）如果对所有 $1 \leq i \leq n$ ，$w1_{i} = w2_{i}$ ，那么它们是相同的方式。

第一行包含两个整数 $n$ 和 $c$ ($0 \leq n \leq 10^{18}, 0 \leq c \leq 1000$) —— Zeyad 想要犯下的罪行数量和他知道的条件数量。 接下来是 $c$ 条条件的定义。有 $26$ 种类型的罪行。每个罪行的定义由罪行类型（一个大写拉丁字母）和其重复次数的限制组成。 每个罪行的重复次数限制是一个正整数，并且所有限制的乘积不超过 $123$ 。输入中可能有重复的条件。 若某罪行的重复次数限制为 $1$ ，无论犯多少次都不会受到惩罚。法律的严格性由其非强制性来弥补。 显然，如果某罪行未在条件集中列出，那么 Zeyad 不会考虑它，因为犯下它不可避免地会受到惩罚。 请不要在 C++ 中使用 %lld 格式符来读写 64 位整数，建议使用 cin 流（你也可以使用 %I64d 格式符）。

输出精确犯下 $n$ 起罪行且不受惩罚的不同方式数量，结果对 $12345$ 取模。

在第一个测试用例中，16 种方式是：AAAAA，AAABB，AABAB，AABBA，ABAAB，ABABA，ABBAA，BAAAB，BAABA，BABAA，BBAAA，ABBBB，BABBB，BBABB，BBBAB，BBBBA。