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.
MOD = 1000000007

def matrix_multiply(A, B):
    rows_A, cols_A = len(A), len(A[0])
    cols_B = len(B[0])
    result = [[0] * cols_B for _ in range(rows_A)]

    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD

    return result

def matrix_power(matrix, n):
    if n == 1:
        return matrix

    if n % 2 == 0:
        half_pow = matrix_power(matrix, n // 2)
        return matrix_multiply(half_pow, half_pow)
    else:
        half_pow = matrix_power(matrix, n // 2)
        return matrix_multiply(matrix_multiply(half_pow, half_pow), matrix)

n, m, k = map(int, input().split())
l = [input() for _ in range(k)]

d = {}
letters = [chr(ord('a') + i) for i in range(26)] + [chr(ord('A') + i) for i in range(26)]

for i in range(m):
    for j in range(m):
        d[letters[i] + letters[j]] = 1
for y in l:
    d[y] = 0

l2 = [d[letters[i] + letters[j]] for i in range(m) for j in range(m)]
matrix = [l2[i:i + m] for i in range(0, m * m, m)]

if n != 1:
    result = matrix_power(matrix, n - 1)
    s = 0
    for row in result:
        for val in row:
            s = (s + val) % MOD
    print(s)
else:
    print(m)
