← 返回题目列表

Codeforces · 222/E

E. 解码基因组

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

最近执行了一项绝密的火星任务。结果,科学家们设法获得了一些有关火星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”不能连续出现两次。