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.
import math

__author__ = 'esadeqia'
import operator


def toInd(c):
    if c.islower():
        return ord(c)-ord('a')
    elif c.isupper():
        return ord(c)-ord('A')+26



def toInd(c):
    x=ord(c)
    if ord('a')<=x and x<=ord('z'):
        return x-ord('a')
    elif ord('A')<=x and x<=ord('Z'):
        return x-ord('A')+26



def emptyMatrix(a,b,value=None):
    return [[value]*b for j in range(a)]


def eyeMatrix(a):
    return [[0]*j+[1]+[0]*(a-j-1) for j in range(a)]

def multiply(A,B,p):
    C=emptyMatrix(len(A),len(B[0]))
    for i in range(len(A)):
        for j in range(len(B[0])):
            t=0
            for k in range(len(B)):
                t+=(A[i][k]*B[k][j])
            C[i][j]=t%p
    return C



def fourSplits(M):
    horizontal=int(len(M)/2)
    vertical=int(len(M[0])/2)
    up=M[:horizontal]
    down=M[horizontal:]


    return (([x[:vertical] for x in up],
             [x[vertical:] for x in up]),

            ([x[:vertical] for x in down],
             [x[vertical:] for x in down]))


def addMatrix(A,B):
    return [list(map(operator.add, A[i], B[i])) for i in range(len(A))]


def subMatrix(A,B):
    assert len(A)==len(B)
    return [
        list(
            map(
                operator.sub, A[i], B[i]))
        for i in range(len(A))]


def allResidual(M,p):
    return [[x%p for x in y]  for y in M]

def strassen(A,B,p):
    if len(A)<2 or len(B)<2 or len(B[0])<2:
        return multiply(A,B,p)
    As=fourSplits(A)
    Bs=fourSplits(B)
    m=[None]*8
    m[1]=strassen(addMatrix(As[0][0],As[1][1]), addMatrix(Bs[0][0],Bs[1][1]),p)
    m[2]=strassen(addMatrix(As[1][0],As[1][1]),     Bs[0][0]          ,p)
    m[3]=strassen(    As[0][0]         , subMatrix(Bs[0][1],Bs[1][1]) ,p)
    m[4]=strassen(    As[1][1]         , subMatrix(Bs[1][0],Bs[0][0]) ,p)
    m[5]=strassen(addMatrix(As[0][0],As[0][1]),     Bs[1][1]          ,p)
    m[6]=strassen(subMatrix(As[1][0],As[0][0]), addMatrix(Bs[0][0],Bs[0][1]),p)
    m[7]=strassen(subMatrix(As[0][1],As[1][1]), addMatrix(Bs[1][0],Bs[1][1]),p)
    C=emptyMatrix(len(A),len(B[0]))
    c11=addMatrix(subMatrix(addMatrix(m[1],m[4]),m[5]),m[7])
    c21=addMatrix(m[3],m[5])
    c12=addMatrix(m[2],m[4])
    c22=addMatrix(addMatrix(subMatrix(m[1],m[2]),m[3]),m[6])
    return allResidual(list(map(operator.concat, c11+c12,c21+c22)),p)



def strassenPower(M,n,p):
    l=len(M)
    newl=int(2**math.ceil(math.log2(l)))
    padding=[0]*(newl-l)
    M=[x+padding for x in M]
    M+=emptyMatrix(newl-l,newl,0)
    # print(l,newl)
    # print(M)
    # exit(0)
    powers=M
    result=eyeMatrix(len(M))
    while n>0:
        # print(n)
        if n%2==1:
            result=strassen(result,powers,p)
        powers=strassen(powers,powers,p)
        n=n>>1
    return result




def fastMethod(n,allowedpairs):
    m=len(allowedPairs)
    result=strassenPower(allowedPairs,n-1,p)
    return sum(map(sum, result))%p

p=1000000007 #(10**9 + 7)
n,m,k=map(int,input().split())
allowedPairs=emptyMatrix(m,m,1)
for i in range(k):
    pair=input()
    allowedPairs[toInd(pair[0])][toInd(pair[1])]=0
resultMain=fastMethod(n,allowedPairs)
print(resultMain)