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

输入描述:

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

输出描述:

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

备注:

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