CF222E 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 \le n \le 10^{15}, 1 \le m \le 52, 0 \le k \le m^2$。