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 sys
# sys.setrecursionlimit(1000000)
input=lambda:sys.stdin.readline().strip()
write=lambda x:sys.stdout.write(str(x)+'\n')

# from decimal import Decimal
# from random import randint
# from copy import deepcopy
from collections import deque,Counter
# from heapq import heapify,heappush,heappop
# from bisect import bisect_left,bisect,insort
from math import inf,sqrt,gcd,pow,ceil,floor,log,log2,log10,pi,sin,cos,tan,asin,acos,atan
# from functools import cmp_to_key
# from itertools import permutations,combinations

def get(s):
    if s>='a':
        return ord(s)-ord('a')
    return ord(s)-ord('A')+26

def binpow(a,b,p):
    res=1
    while b:
        if b&1:
            res=res*a%p
        a=a*a%p
        b>>=1
    return res

def mul1(a,b):
    res=[0]*m
    for i in range(m):
        for j in range(m):
            res[i]+=a[j]*b[j][i]
    return res

def mul2(a,b):
    res=[[0]*m for i in range(m)]
    for i in range(m):
        for j in range(m):
            for k in range(m):
                res[i][j]+=a[i][k]*b[k][j]
    return res

def solve(n,m,k):
    matrix=[[1]*m for i in range(m)]
    for i in range(k):
        a,b=map(get,list(input()))
        matrix[a][b]=0
    now=[1]*m
    n-=1
    while n:
        if n&1:
            now=mul1(now,matrix)
        matrix=mul2(matrix,matrix)
        n>>=1
    return sum(now)%mod

n,m,k=map(int,input().split())
mod=1000000007
print(solve(n,m,k))