CF107D.Crime Management

Zeyad wants to commit n crimes in Egypt and not be punished at the end. There are several types of crimes. For example, bribery is a crime but is not considered such when repeated twice. Therefore, bribery is not considered a crime when repeated an even number of times. Speeding is a crime, but is not considered such when repeated a number of times which is a multiple of five.

More specifically, c conditions on crime repetitions are known. Each condition describes the crime type t__i and its multiplicity m__i. If the number of times Zeyad committed the crime t__i is a multiple of m__i, Zeyad will not be punished for crime t__i. Some crimes may be listed more than once. In this case fulfilling at least one condition for this crime is enough to not be punished for it. Of course, if for certain crime the number of times Zeyad committed it is zero, he is innocent with respect to this crime.

Now Zeyad is interested in a number of ways he can commit exactly n crimes without any punishment.

The order of commiting the crimes matters. More formally, two ways, sequences _w_1 and _w_2, of committing n crimes are equal if w_1_i = w_2_i, for all 1 ≤ i ≤ n.

泽亚德希望在埃及实施恰好 $ n $ 起犯罪行为，且最终不受到任何惩罚。犯罪行为有多种类型。例如，“行贿”是一种犯罪，但若重复实施两次，则不被视为犯罪；因此，当“行贿”被实施偶数次时，不构成犯罪。“超速驾驶”也是一种犯罪，但若实施次数是 $ 5 $ 的倍数，则不被视为犯罪。

更具体地，已知存在 $ c $ 个关于犯罪实施次数的约束条件。每个条件描述一种犯罪类型 $ t_i $ 及其对应的倍数 $ m_i $。若泽亚德对犯罪类型 $ t_i $ 的实施次数是 $ m_i $ 的倍数，则他不会因该类犯罪而受罚。某些犯罪类型可能在约束条件中多次出现；此时，只要满足其中至少一个条件，即可免于因该类犯罪而受罚。当然，若某类犯罪的实施次数为零，则泽亚德在该类犯罪上自然是清白的。

现在，泽亚德想知道：他有多少种方式可以恰好实施 $ n $ 起犯罪行为，且完全避免惩罚？

犯罪行为的实施顺序是重要的。更准确地说，两个实施 $ n $ 起犯罪的序列 $ w_1 $ 和 $ w_2 $ 被视为相同，当且仅当对所有 $ 1 \le i \le n $，均有 $ w_{1,i} = w_{2,i} $。

The first line contains two integers n and c (0 ≤ n ≤ 1018, 0 ≤ c ≤ 1000) — the number of crimes Zeyad would like to commit and the number of conditions he is aware of.

Then the definitions for c conditions follow. There are 26 types of crimes. Each crime definition consists of crime type — a capital Latin letter — and its multiplicity.

The multiplicity of each crime is a positive integer number and the product of all multiplicities does not exceed 123. Some conditions may be repeated in the input more than once.

Crime of multiplicity 1 is not yielding any punishment regardless of the number of times it was committed. The strictness of the law is compensated by the fact that it's non-mandatory.

Obviously, if some crime is not listed in the set of conditions, then Zeyad will not consider it, as committing it would unavoidably lead to the punishment.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin stream (you may also use the %I64d specificator).

第一行包含两个整数 $n$ 和 $c$（$0 \le n \le 10^{18}$，$0 \le c \le 1000$）——分别表示泽亚德希望实施的犯罪数量，以及他所知晓的约束条件数量。

接下来是 $c$ 个约束条件的定义。共有 26 种犯罪类型。每个犯罪定义由犯罪类型（一个大写拉丁字母）及其重数（multiplicity）组成。

每种犯罪的重数是一个正整数，且所有重数的乘积不超过 $123$。输入中某些约束条件可能出现多次。

重数为 $1$ 的犯罪，无论实施多少次，均不会招致任何惩罚。法律的严格性由其非强制性予以补偿。

显然，若某种犯罪未在约束条件集合中列出，则泽亚德将不予考虑，因为实施该犯罪必将导致惩罚。

请注意：在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin 流（也可使用 %I64d 格式说明符）。

Output the number of different ways Zeyad can commit exactly n crimes with no punishment modulo 12345.

输出Zeyad恰好实施 $n$ 起犯罪且不受到惩罚的不同方式数目，对 12345 取模。

In the first test case, the 16 ways are: AAAAA, AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA, ABBBB, BABBB, BBABB, BBBAB, BBBBA.

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