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.
q   = int(1e9)+7
def binpower(A1,e):
    n   = len(A1)
    r   = range(n)
    A2  = [[0]*n for _ in r]
    C1  = [[0]*n for _ in r]
    C2  = [[0]*n for _ in r]
    for i in r: C1[i][i]=1
    sA1,sC1 = True,True
    while True:
        C = C1 if sC1 else C2
        A = A1 if sA1 else A2
        if e &1:
            T = C2 if sC1 else C1
            for i in r:
                for j in r:
                    T[i][j] = sum([A[i][k]*C[k][j] for k in r])%q
            sC1 = not sC1
        e = e>>1
        if e==0: return T
        S = A2 if sA1 else A1
        for i in r:
            for j in r:
                S[i][j] = sum([A[i][k]*A[k][j] for k in r])%q 
        sA1 = not sA1

c2i = lambda c: ord(c)-ord('a') if c.islower() else ord(c)-ord('A')+26
def f(l1,l2):
    n,m,_ = l1
    if n==1: return m
    M  = [[1]*m for _ in range(m)]
    for s in l2:
        i = c2i(s[0])
        j = c2i(s[1])
        M[i][j]=0
    return sum([sum(l) for l in binpower(M,n-1)])

l1  =  list(map(int,input().split()))
l2  = [input() for _ in range(l1[2])]
print(f(l1,l2)%q)

