扎亚德想在埃及犯下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。