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.
def mat_mul(A,B):
  row=len(A)
  column=len(B[0])
  internal=len(A[0]) 
  C=[]
  for i in range(row):
    C.append([0]*column)
  for i in range(row):
    for j in range(column):
      for k in range(internal):
        C[i][j]+=A[i][k]*B[k][j]
  return C

def mat_pow(A,n):
  dim=len(A)
  B=A.copy()
  C=[]
  for i in range(dim):
    C.append([0]*dim)
    C[i][i]=1
  while n>0:
    if (n%2)==1:
      C=mat_mul(B,C)
    B=mat_mul(B,B)
    n=n//2
  return C

def tran_mat(m,pairlist):
  A=[]
  for i in range(m):
    A.append([1]*m)
  for pair in pairlist:
    i=ord(pair[1])-ord('a')
    if i<0: i+=(32+26)
    j=ord(pair[0])-ord('a')
    if j<0: j+=(32+26)
    A[i][j]=0
  return A

def column_one(m):
  A=[]
  for i in range(m):
    A.append([1])
  return A

def ans(C):
  a=0
  for r in C:
    a+=r[0]
  return a 

if __name__=='__main__':
  n,m,k=[int(x) for x in input().split()]
  pairlist=[]
  for i in range(k):
    pairlist.append(input())
  A=tran_mat(m,pairlist)
  B=column_one(m)
  C=mat_mul(mat_pow(A,n-1),B)
  print(ans(C))