最近执行了一项绝密的火星任务。结果,科学家们设法获得了一些有关火星DNA的信息。现在我们知道任何火星 DNA 最多包含 m 个不同的核苷酸,编号从 1 到 m。火星 DNA 的特殊特性阻止了一些核苷酸对在这条链中连续出现。例如,如果核苷酸1和核苷酸2在火星DNA中不能连续出现,则核苷酸链[1, 2]不是火星DNA的有效链,但核苷酸链[2, 1]可以是有效链(如果没有相应的限制)。 DNA 链中不能连续出现的核苷酸对的数量为 k。
基因研究需要有关火星 DNA 的正确 n 长链数量的信息。您的任务是编写一个程序来计算该值。
输入
第一行包含三个空格分隔的整数 n、m、k (1 ≤ n ≤ 1015、1 ≤ m ≤ 52、0 ≤ k ≤ m2)。
接下来的 k 行每行包含两个字符,它们之间没有空格,代表禁止的核苷酸对。第一个字符代表禁止对中的第一个核苷酸,第二个字符代表第二个核苷酸。
编号为1至26的核苷酸由英文字母“a”至“z”表示(1是“a”,2是“b”,...,26是“z”)。编号为27至52的核苷酸由从“A”至“Z”的英文字母表示(27是“A”,28是“B”,...,52是“Z”)。
保证每个禁止对在输入中最多出现一次。保证所有禁止对中的核苷酸数量不能超过m。请注意,核苷酸对中的顺序很重要。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
打印一个整数 — 所求数字模 1000000007 (109 + 7)。
示例
输入 #1
3 3 2 ab ba
输出 #1
17
输入 #2
3 3 0
输出 #2
27
输入 #3
2 1 1 aa
输出 #3
0
注意
在第二个测试用例中,允许所有可能的三核苷酸 DNA。每个核苷酸可以取三个值之一,因此总共有 27 个不同的三核苷酸 DNA。
在第三个测试样本中,我们无法制造任何由两个核苷酸组成的 DNA——唯一可能的核苷酸“a”不能连续出现两次。