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<sup class="upper-index">15</sup>, 1 ≤ *m* ≤ 52, 0 ≤ *k* ≤ *m*<sup class="upper-index">2</sup>).

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.
# How many ways to generate length-N array where elements can take one of m values (m <= 52; denoted a..z,A..Z)
# s.t. none of k ordered value pair appears:
# e.g. ab = ab can't appear but ba can; aa = aa can't appear

# Input: N (N < 10^18), m (n<=52), k patterns 0 <= k <= m^2

# E.g.
# N=3, m=3, k=2
# ab
# ba
# -> return 17

# Ideas
# * divide and conquer
# * for each n, memo[n][i][j] = number of paths of length n satisfying bans, that start at i and end at j

MOD = 1000000007

def _solve(n, m, ban, memo):
	if n in memo: return memo[n]
	if n == 0: return [[0]*m for _ in range(m)]
	if n == 1:
		memo[n] = [[0]*m for _ in range(m)]
		for i in range(m):
			memo[n][i][i] = 1
		return memo[n]

	left, right = _solve(n // 2, m, ban, memo), _solve(n - n // 2, m, ban, memo)
	memo[n] = [[0]*m for _ in range(m)]

	# count all paths starting at i, ending at j
	for i in range(m):
		for j in range(m):
			memo[n][i][j] = sum(left[i])*sum(right[s][j] for s in range(m)) % MOD

	# subtract left path ending at x * right path ending at y for each banned pair (x, y)
	for x, y in ban:
		for i in range(m):
			for j in range(m):
				memo[n][i][j] -= left[i][x] * right[y][j] % MOD
				memo[n][i][j] += MOD
				memo[n][i][j] %= MOD
	
	return memo[n]
	

def solve(n, m, ban):
	counts = _solve(n, m, ban, {})
	return sum(sum(row) for row in counts)%MOD


def main():
	from sys import stdin

	n, m, k = list(map(int, stdin.readline().strip().split()))

	ban = set()
	for _ in range(k):
		x, y = list(stdin.readline().strip())
		x = ord(x)-97 if 'a' <= x <= 'z' else ord(x)-39
		y = ord(y)-97 if 'a' <= y <= 'z' else ord(y)-39
		ban.add((x,y))

	out = solve(n, m, ban)
	print('{}'.format(out))


if __name__ == '__main__':
	main()


