← 返回题目列表

Codeforces · 107/D

D. 犯罪管理

中文机器翻译题面 查看原题

扎亚德想在埃及犯下n项罪行,但最终不会受到惩罚。犯罪有几种类型。例如,贿赂是一种犯罪,但重复两次则不被视为犯罪。因此,行贿行为重复次数为偶数时,不构成犯罪。超速驾驶属于犯罪行为,但重复次数达到五的倍数时,则不被视为犯罪行为。

更具体地说,犯罪重复的c条件是已知的。每个条件描述了犯罪类型 ti 及其多重性 mi。如果 Zeyad 犯罪 ti 的次数是 mi 的倍数,则 Zeyad 不会因犯罪 ti 受到惩罚。有些罪行可能会被多次列出。在这种情况下,至少满足该犯罪的一个条件就足以免受惩罚。当然,如果对于某种犯罪,扎亚德犯下的次数为零,那么他就该犯罪是无辜的。

现在,Zeyad 对他可以犯下 n 种罪行而不受任何惩罚的多种方式感兴趣。

犯罪顺序很重要。更正式地说,如果 w1i = w2i(对于所有 1 ≤ i ≤ n),犯下 n 项罪行的两种方式(序列 w1 和 w2)是相等的。

输入

第一行包含两个整数 n 和 c (0 ≤ n ≤ 1018, 0 ≤ c ≤ 1000) — Zeyad 想要实施的犯罪数量以及他知道的情况数量。

然后是 c 条件的定义。有26种犯罪。每个犯罪定义都由犯罪类型(一个大写拉丁字母)及其多重性组成。

每个犯罪的重数为正整数,所有重数的乘积不超过123。某些条件可能在输入中重复多次。

重数 1 犯罪无论犯下多少次都不会受到任何惩罚。法律的严格性因其非强制性而得到补偿。

显然,如果某种犯罪行为没有被列入条件组中,那么Zeyad就不会考虑它,因为犯下这种行为将不可避免地导致惩罚。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin 流(您也可以使用 %I64d 指定符)。

输出

输出 Zeyad 可以犯下 n 种罪行且不受惩罚的不同方式的数量,以 12345 为模。

示例

输入 #1

5 2
A 1
B 2

输出 #1

16

输入 #2

6 3
A 1
B 2
C 3

输出 #2

113

输入 #3

8 3
A 2
A 3
B 2

输出 #3

128

注意

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