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.

Input

The first line contains three space-separated integers n, m, k (1 ≤ n ≤ 1015, 1 ≤ m ≤ 52, 0 ≤ k ≤ m2).

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.

Output

Print a single integer — the sought number modulo 1000000007 (109 + 7).

Examples

Input

3 3 2
ab
ba


Output

17


Input

3 3 0


Output

27


Input

2 1 1
aa


Output

0

Note

In the second test case all possible three-nucleotide DNAs are permitted. Each nucleotide can take one of three values, thus in total there are 27 distinct three nucleotide DNAs.

In the third test sample we cannot make any DNA of two nucleotides — the only possible nucleotide "a" cannot occur two times consecutively.
import java.awt.geom.Line2D;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.TreeSet;



public class Solution 
{
    public static void main(String[] args) {
        //      FasterScanner in=new FasterScanner();
        //      PrintWriter out=new PrintWriter(System.out);
        //      int t=in.nextInt();
        //      for(int ii=0;ii<t;ii++)
        //      {
        new Solution().solve();
        //      }//System.out.println(Long.MIN_VALUE);
        //      out.close();

    }
    public Solution()
    {
        in=new FasterScanner();
        out=new PrintWriter(System.out);
    }

    //    public Solution(FasterScanner in,PrintWriter out)
    //    {
    //        this.in=in;
    //        this.out=out;
    //    }

       FasterScanner in;
    //Scanner in;
    PrintWriter out;
    //  segmentTree t;
    //  segmentTree c;
    long mod=1000000007L ;
    //  long[] arr;
    //  Hashtable<Long, Integer> table;
    //  int d;
    //  int[] count;
    //  int n;
    public void solve()
    {
        
    //      BigInteger n=new BigInteger(in.next());
            long n=in.nextLong()-1;
            
            int m=in.nextInt();
            long kk=in.nextLong();
            String n2=Long.toBinaryString(n);
                        
//          int[][] arr=new int[1<<m][m];
//          for(int i=0;i<arr.length;i++)
//          {
//              String s=Integer.toBinaryString(i);
//              int cc=m-1;
//              for(int j=s.length()-1;j>=0;j--)
//              {
//                  arr[i][cc--]=s.charAt(j)-'0';
//              }
//              //      System.out.println(Arrays.toString(arr[i]));
//          }

            long[][] a=new long[m][m];

            for(int i=0;i<a.length;i++)
            {
                Arrays.fill(a[i], 1);
            }
            
            for(int i=0;i<kk;i++)
            {
                String ss=in.nextLine();
                char c1=ss.charAt(0);
                char c2=ss.charAt(1);
                int cc1='a';
                int cc2='b';
                if(c1>='a')
                {
                    cc1=c1-'a';
                }
                else
                {
                    cc1=c1-'A'+26;
                }
                if(c2>='a')
                {
                    cc2=c2-'a';
                }
                else
                {
                    cc2=c2-'A'+26;
                }
                a[cc2][cc1]=0;
            }

            if(n==0)
            {
                System.out.println(m);
                return;
            }
            
            long[][] ans=new long[a.length][a.length];

            for(int i=0;i<a.length;i++)
            {
                for(int j=0;j<a[i].length;j++)
                {
                    ans[i][j]=a[i][j];
                }
            }

            for(int i=1;i<n2.length();i++)
            {
                ans=mul(ans,ans,mod);
                if(n2.charAt(i)=='1')
                {
                    ans=mul(ans,a,mod);
                }
            }

            long ansx=0;
            for(int i=0;i<ans.length;i++)
            {
                for(int j=0;j<ans[0].length;j++)
                {
                    ansx+=ans[i][j];
                    ansx%=mod;
                }
            }

            out.println(ansx);
        
        out.close();
    }


    public long[][] mul(long[][] s1,long[][] s2,long mod)
    {
        long[][] ans=new long[s1.length][s2[0].length];
        for(int i=0;i<ans.length;i++)
        {
            for(int j=0;j<ans[0].length;j++)
            {
                for(int k=0;k<s1.length;k++)
                {
                    ans[i][j]+=s1[i][k]*s2[k][j];
                    ans[i][j]%=mod;
                }
            }
        }
        return ans;
    }


    public class ss implements Comparable<ss>
    {
        long val;
        int idx;
        int dpidx;
        public ss(long v,int i)
        {
            this.val=v;
            this.idx=i;
        }
        @Override
        public int compareTo(ss o) {
            // TODO Auto-generated method stub
            if(this.val!=o.val)
            {
                return Long.compare(this.val, o.val);
            }
            else
            {
                return Long.compare(this.idx, o.idx);
            }
        }

        public String toString()
        {
            return " { "+this.idx+" "+this.val+" "+this.dpidx+" } ";
        }
    }

    //source http://codeforces.com/blog/entry/18051
    class segmentTree
    {
        int n;  // array size
        long t[];

        public segmentTree(long[] arr)
        {
            n=arr.length;
            t=new long[3*n];
            for(int i=0;i<n;i++)
            {
                t[n+i]=arr[i];
            }
            build();
        }

        public void print()
        {
            for(int i=n;i<=n+15;i++)
            {
                out.print(t[i]+" ");
            }
            out.println();
        }

        void build() {  // build the tree
            for (int i = n - 1; i > 0; --i) t[i] = Math.max(t[i<<1] , t[i<<1|1]);
        }

        void modify(int p, long value) {  // set value at position p
            for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = Math.max(t[p] , t[p^1]);
        }

        long query(int l, int r) {  // sum on interval [l, r)
            long res = 0;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if ((l&1)!=0) res = Math.max(res,t[l++]);
                if ((r&1)!=0) res = Math.max(t[--r],res);
            }
            return res;
        }
    }

    public class Node
    {
        int start;
        int stop;
        int val;
        Node left;
        Node right;

        int lazy;

        public Node(int start,int stop,int[] arr)
        {
            this.start=start;
            this.stop=stop;
            if(this.start==this.stop)
            {
                //TODO
                this.val=arr[start];
            }
            else
            {
                left=new Node(start,(start+stop)/2,arr);
                right=new Node((start+stop)/2+1,stop,arr);
                //TODO
                this.val=left.val+right.val;
            }
        }

        //      public void update(int idx,int v)
        //      {
        //          if(this.start==this.stop)
        //          {
        //              if(this.start==idx)
        //              {
        //                  this.val+=v;
        //              }
        //          }
        //          else
        //          {
        //              if(this.start<=idx && this.stop>=idx)
        //              {
        //                  left.update(idx, v);
        //                  right.update(idx, v);
        //                  this.val=left.val+right.val;
        //              }
        //          }
        //      }

        public int lazyUpdate(int l,int r)
        {
            if(l>r)
            {
                return 0;
            }
            if(this.start==this.stop)
            {
                if(l<=this.start && this.start<=r)
                {
                    this.val^=1;
                    return this.val;
                }
                else
                {
                    return this.val;
                }
            }
            else if(this.start>r || this.stop<l)
            {
                return this.val;
            }
            else if(this.start>=l && this.stop<=r)
            {
                this.lazy=1-this.lazy;
                this.val=this.stop-this.start+1-this.val;
                return this.val;
            }
            else
            {
                if(this.lazy==0)
                {
                    //left.query(l, r)+right.query(l, r);
                    this.val=left.lazyUpdate(l, r);
                    this.val+=right.lazyUpdate(l, r);
                }
                else
                {
                    this.lazy=0;
                    left.lazyUpdate(start,stop);
                    right.lazyUpdate(start, stop);
                    this.val=left.lazyUpdate(l, r);
                    this.val+=right.lazyUpdate(l, r);
                }
                return this.val;
            }
        }

        public int query(int l,int r)
        {
            if(l>r)
            {
                return 0;
            }
            if(this.start==this.stop)
            {
                if(l<=this.start && this.start<=r)
                {
                    return this.val;
                }
                else
                {
                    return 0;
                }
            }
            else if(this.start>r || this.stop<l)
            {
                return 0;
            }
            else if(this.start>=l && this.stop<=r)
            {
                return this.val;
            }
            else
            {
                if(this.lazy==0)
                {
                    return left.query(l, r)+right.query(l, r);
                }
                else
                {
                    this.lazy=0;
                    this.val=left.lazyUpdate(start,stop);
                    this.val+=right.lazyUpdate(start, stop);
                    return left.query(l, r)+right.query(l, r);
                }
            }
        }
    }


    public class UF {

        private int[] parent;  // parent[i] = parent of i
        private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
        private int count;   
        int[] seg;
        int max;
        // number of components
        public UF(int N) {
            if (N < 0) throw new IllegalArgumentException();
            count = N;
            parent = new int[N];
            rank = new byte[N];
            seg=new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                rank[i] = 0;
                seg[i]=1;
            }
            max=1;
        }

        public int find(int p) {
            if (p < 0 || p >= parent.length) throw new IndexOutOfBoundsException();
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];    // path compression by halving
                p = parent[p];
            }
            return p;
        }

        public int count() {
            return count;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        public boolean union(int p, int q) {
            //  System.out.println("uf "+p+" "+q);
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return false;

            // make root of smaller rank point to root of larger rank
            if      (rank[rootP] < rank[rootQ])
            {
                parent[rootP] = rootQ;
                seg[rootQ]+=seg[rootP];
                max=Math.max(seg[rootQ],max);
            }
            else if (rank[rootP] > rank[rootQ])
            {
                parent[rootQ] = rootP;
                seg[rootP]+=seg[rootQ];
                max=Math.max(seg[rootP],max);
            }
            else {
                parent[rootQ] = rootP;
                rank[rootP]++;
                seg[rootP]+=seg[rootQ];
                max=Math.max(seg[rootP],max);
            }
            count--;
            return true;
        }

    }



    long pow(long a,int n,long m)
    {
        if(n==1)
            return a;
        if(n==0)
            return 1;
        long ans=pow(a,n/2,m);
        ans*=ans;
        ans%=m;
        if(n%2!=0)
            ans*=a;
        ans%=m;
        return ans;
    }

    public static int gcd(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }




    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
} 