Decoding Genome

题意翻译

## 题目描述 最近，对火星的一次秘密研究拉开帷幕，在这次探寻中，科学家们发现了火星上的DNA。 他们发现，火星DNA包含 $n$ 个核苷酸，且由 $m$ 种不同核苷酸构成（编号为 $1$~$m$）。 他们还发现出于某些特殊的原因，存在 $k$ 对核苷酸，一对这样的核苷酸不会连续出现在火星DNA中。 > 例如存在一对这样的核苷酸 (1,2) ，则核苷酸2不能紧连着核苷酸1（即DNA中不会连续出现 1,2）；但是可以连续出现 2,1 科学家们想知道有多少种不同的火星DNA（如果两个DNA存在一个位置，使得两个DNA的该位置的核苷酸不同，则认为这两个DNA不同）。 ## 输入 第一行包含 $3$ 个整数 $n,m,k$ ，含义见题目描述； 接下来 $k$ 行，每行包含一个长度为 $2$ 的字符串，字符串由小写字母和大写字母构成——字母'a'~'z'表示核苷酸 $1$~$26$，'A'~'Z'表示核苷酸 $27$~$52$；表示题目描述中的 $k$ 对核苷酸。 ## 输出 一个整数，表示有多少种不同的DNA，答案对 $(10^9+7)$ 取模。 ## 数据规模 $1\leq n\leq 10^{15},1\leq m\leq 52,0\leq k\leq m^2$。

题目描述

Recently a top secret mission to Mars has taken place. As a result, scientists managed to obtain some information about the Martian DNA. Now we know that any Martian DNA contains at most $ m $ different nucleotides, numbered from $ 1 $ to $ m $ . Special characteristics of the Martian DNA prevent some nucleotide pairs from following consecutively in this chain. For example, if the nucleotide 1 and nucleotide 2 can not follow consecutively in the Martian DNA, then the chain of nucleotides \[1, 2\] is not a valid chain of Martian DNA, but the chain of nucleotides \[2, 1\] can be a valid chain (if there is no corresponding restriction). The number of nucleotide pairs that can't follow in the DNA chain consecutively, is $ k $ . The needs of gene research required information about the quantity of correct $ n $ -long chains of the Martian DNA. Your task is to write a program that will calculate this value.

输入输出格式

输入格式

The first line contains three space-separated integers $ n,m,k $ ( $ 1<=n<=10^{15} $ , $ 1<=m<=52 $ , $ 0<=k<=m^{2} $ ). Next $ k $ lines contain two characters each, without a space between them, representing a forbidden nucleotide pair. The first character represents the first nucleotide in the forbidden pair, the second character represents the second nucleotide. The nucleotides with assigned numbers from 1 to 26 are represented by English alphabet letters from "a" to "z" (1 is an "a", 2 is a "b", $ ... $ , 26 is a "z"). Nucleotides with assigned numbers from 27 to 52 are represented by English alphabet letters from "A" to "Z" (27 is an "A", 28 is a "B", $ ... $ , 52 is a "Z"). It is guaranteed that each forbidden pair occurs at most once in the input. It is guaranteed that nucleotide's numbers in all forbidden pairs cannot be more than $ m $ . Note that order is important in nucleotide pairs. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

输出格式

Print a single integer — the sought number modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

3 3 2
ab
ba

输出样例 #1

17

输入样例 #2

3 3 0

输出样例 #2

27

输入样例 #3

2 1 1
aa

输出样例 #3

0

说明

In the second test case all possible three-nucleotide DNAs are permitted. Each nucleotide can take one of three values, thus in total there are 27 distinct three nucleotide DNAs. In the third test sample we cannot make any DNA of two nucleotides — the only possible nucleotide "a" cannot occur two times consecutively.