在上世纪八十年代，英国生物学家谢多雷克博士在他的新著《生命的
新科学》中提出了一种“形态形成场”理论。他认为，不只声音会产生共
鸣，事件也会产生共鸣。他将连续发生同类事件的场所称为“形态形成场”
(morphogenetic eld)，将所发生的同类事件称为“形态共鸣”。
𝐾𝑢𝑟𝑎𝑠ℎ𝑖𝑘𝑖 𝐴𝑘𝑎𝑛𝑒天生具有利用形态场和另外世界线另外时间点的自
己通信的能力，即所谓的高次元生物。
𝐴𝑘𝑎𝑛𝑒打算和一名民科人士交流学术，但对方的手机常常绑在微波炉
上，所以所有短信都必须加密处理。
短信中将会涉及前𝑘种大写字母，每个大写字母都有一个对应的替换
式𝑆_𝑖，替换式中只会出现大写字母和数字，格式详见样例。
比如𝐴 → 𝐵𝐵,𝐵 → 𝐶𝐶0,𝐶 → 123，代表𝐴 = 12312301231230,𝐵 =
1231230,𝐶 = 123。
现在对于给定的替换式，求字符𝐴所代表的串有多少子串满足：
∙ 这个子串为单个字符‘0’或没有前导‘0’。
∙ 把这个子串看作一个十进制数后模𝑛等于0。
答案对𝑟取模。

第一行，两个正整数𝑛, 𝑟。
第二行，一个正整数𝑘。
接下来𝑘行，每行一个替换式𝑆𝑖，保证依次给出。

一行，一个整数，满足条件的子串数。

2 1000000000
1
A->000002

6

2 1000000000
3
A->BB
B->CC0
C->123

46

对于20%的数据，最终串A长度≤ 150。
对于50%的数据，最终串A长度≤ 105。
对于70%的数据，不出现‘0’字符。
对于100%的数据，2 ≤ 𝑛 ≤ 30，2 ≤ 𝑟 ≤ 109，1 ≤ 𝑘 ≤ 26，4 ≤ |𝑆𝑖| ≤100。