Limak is a little polar bear. Polar bears hate long strings and thus they like to compress them. You should also know that Limak is so young that he knows only first six letters of the English alphabet: 'a', 'b', 'c', 'd', 'e' and 'f'.

You are given a set of q possible operations. Limak can perform them in any order, any operation may be applied any number of times. The i-th operation is described by a string a_{i} of length two and a string b_{i} of length one. No two of q possible operations have the same string a_{i}.

When Limak has a string s he can perform the i-th operation on s if the first two letters of s match a two-letter string a_{i}. Performing the i-th operation removes first two letters of s and inserts there a string b_{i}. See the notes section for further clarification.

You may note that performing an operation decreases the length of a string s exactly by 1. Also, for some sets of operations there may be a string that cannot be compressed any further, because the first two letters don't match any a_{i}.

Limak wants to start with a string of length n and perform n - 1 operations to finally get a one-letter string "a". In how many ways can he choose the starting string to be able to get "a"? Remember that Limak can use only letters he knows.


-----Input-----

The first line contains two integers n and q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) — the length of the initial string and the number of available operations.

The next q lines describe the possible operations. The i-th of them contains two strings a_{i} and b_{i} (|a_{i}| = 2, |b_{i}| = 1). It's guaranteed that a_{i} ≠ a_{j} for i ≠ j and that all a_{i} and b_{i} consist of only first six lowercase English letters.


-----Output-----

Print the number of strings of length n that Limak will be able to transform to string "a" by applying only operations given in the input.


-----Examples-----
Input
3 5
ab a
cc c
ca a
ee c
ff d

Output
4

Input
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c

Output
1

Input
6 2
bb a
ba a

Output
0



-----Note-----

In the first sample, we count initial strings of length 3 from which Limak can get a required string "a". There are 4 such strings: "abb", "cab", "cca", "eea". The first one Limak can compress using operation 1 two times (changing "ab" to a single "a"). The first operation would change "abb" to "ab" and the second operation would change "ab" to "a".

Other three strings may be compressed as follows:   "cab" $\rightarrow$ "ab" $\rightarrow$ "a"  "cca" $\rightarrow$ "ca" $\rightarrow$ "a"  "eea" $\rightarrow$ "ca" $\rightarrow$ "a" 

In the second sample, the only correct initial string is "eb" because it can be immediately compressed to "a".

Difficulty: competition

Starter code:

Solutions:
n, q = list(map(int, input().split()))
go = dict()
for i in range(q):
    fr, to = input().split()
    go[fr] = to

ans = 0

for i in range(6 ** n):
    cur = i
    s = ''
    for j in range(n):
        s += chr(ord('a') + (cur % 6))
        cur //= 6

    while len(s) > 1:
        fr = s[:2]
        if fr not in go:
            break
        s = go[fr] + s[2:]

    if s == 'a':
        ans += 1

print(ans)


3

ans = set()

def gen(cur, n, ops):
    if len(cur) == n:
        ans.add(cur)
    else:
        for t in ops[ord(cur[0]) - ord("a")]:
            gen(t + cur[1:], n, ops)


n, q = list(map(int, input().split()))
ops = [[] for i in range(6)]
for i in range(q):
    s, t = input().split()
    ops[ord(t[0]) - ord('a')].append(s)

gen("a", n, ops)
print(len(ans))


#! /usr/bin/env python3
from collections import defaultdict

def main():
    n, q = list(map(int, input().split()))
    instrs = [input().split() for _ in range(q)]

    instr_dict = defaultdict(list)
    for src, dest in instrs:
        instr_dict[dest].append(src)

    strs = set()
    last_q = set('a')
    for _ in range(n - 1):
        next_q = set()
        for s in last_q:
            rules = instr_dict[s[0]]
            s = s[1:]
            for rule in rules:
                next_q.add(rule + s)
        last_q = next_q

    print(len(last_q))

main()


from itertools import product as comb

word = "abcdef"
n, q = list(map(int, input().split()))
rep = dict()
for _ in range(q):
    k, v = input().split()
    rep[k] = v
ret = set()
for x in comb(word, repeat=n):
    tmp = "".join(x)
    while len(tmp) > 1:
        before = tmp
        if tmp[:2] not in rep:
            break
        tmp = rep[tmp[:2]] + tmp[2:]
    if tmp == "a":
        ret.add(x)
print(len(ret))


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

pat = {}

(n, q) = (int(i) for i in input().split())
for i in range(q):
    (a, b) = [i for i in input().split()]
    if b in list(pat.keys()):
        pat[b].append(a)
    else:
        pat[b] = [a]

start = time.time()

str = ['a']
for i in range(n-1):
    newstr = []
    for j in range(len(str)):
        l = str[j][0]
        if l in list(pat.keys()):
            for k in pat[l]:
                newstr.append(k+str[j][1:])

    str = newstr
    if len(str) == 0:
        break

print(len(str))
finish = time.time()
#print(finish - start)


from functools import reduce

n, q = [int(x) for x in input().split()]

substitutions = {}

for _ in range(q):
    from_str, to_str = input().split()

    if to_str in substitutions:
        substitutions[to_str].append(from_str)
    else:
        substitutions[to_str] = [from_str]


def generate_str(start_str):
    if len(start_str) == n:
        return 1

    if start_str[0] not in substitutions:
        return 0

    result = 0
    for variant in substitutions[start_str[0]]:
        result += generate_str(variant + start_str[1:])

    return result

print(generate_str('a'))


from collections import defaultdict
from itertools import product


def generate_strings(n):
    for s in product("abcdef", repeat = n):
        yield ''.join(s)

def compress(s, d):
    while len(s) > 1:
        p = s[:2]
        if p not in d:
            break
        s = d[p] + s[2:]
    return s

def solve(n, d):
    return sum(compress(s, d) == "a" for s in generate_strings(n))

n, q = list(map(int, input().split()))

d = defaultdict(str)

for i in range(q):
    s1, s2 = input().split()
    d[s1] = s2

print(solve(n, d))


n,q=map(int,input().split())
d={}
ch=set()
ans=set()
for i in range(q):
    a,b=input().split()
    d.setdefault(b,set()).add(a)
ch={"a"}
 
while ch!=set():
    b=ch.pop()
    if len(b)==n: ans.add(b); continue
    for a in d.setdefault(b[0],set()):
        ch.add(''.join((a,b[1:])))
print(len(ans))

n, q = map(int, input().split())

fr = dict()
for i in range(q):
    a, b = input().split()
    if b in fr:
        fr[b].append(a)
    else:
        fr[b] = [a]


def dfs(c, cnt):
    nonlocal n
    if cnt == n:
        return 1
    if cnt > n:
        return 0
    
    nonlocal fr
    if c not in fr:
        return 0
    
    ans = 0
    for i in fr[c]:
        ans += dfs(i[0], cnt+1)
    return ans


print(dfs('a', 1))

def deep(ch, curn):
    s = 0
    for i in d[ch]:
        if i[0] in 'abcdef' and i[1] in 'abcdef':
            if curn and i[0] in d:
                s += deep(i[0], curn-1)
            elif curn == 0:
                s += 1
    return s

n, m = list(map(int, input().split()))
d = {}
for i in range(m):
    dec, en = input().split()
    if en in d:
        d[en].append(dec)
    else:
        d[en] = [dec]
if n == 1:
    print(1)
elif 'a' in d:
    print(deep('a', n-2))
else:
    print(0)


import collections

n, q = [int(x) for x in input().split()]
g = dict()
for i in range(q):
    to, f = input().split()
    if f in g: g[f].append(to)
    else: g[f] = [to]
counts = dict()
def count(s):
    if s in counts: return counts[s]
    if len(s) == n:
        counts[s] = 1
        return 1
    if len(s) > n: return 0
    c = s[0]
    cnt = 0
    if not c in g: return 0
    suff = s[1:]
    for j in g[c]:
        new_s = j + suff
        cnt += count(new_s)
    counts[s] = cnt
    return cnt
print(count('a'))


#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

import collections
import itertools


Operation = collections.namedtuple("Operation", "from_str to_str")


def is_feasible_operation(base_str, operation):
    return base_str.startswith(operation.from_str)


def conduct_operation(base_str, operation):
    return base_str.replace(operation.from_str, operation.to_str, 1)


def breadth_first_search(init_str, operations):
    q = collections.deque()
    q.append(init_str)
    visited = collections.defaultdict(bool)
    visited[init_str] = True
    while q:
        base_str = q.popleft()
        if base_str == "a":
            return True
        for operation in operations:
            if not is_feasible_operation(base_str, operation):
                continue
            new_str = conduct_operation(base_str, operation)
            if not visited[new_str]:
                visited[new_str] = True
                q.append(new_str)
    return False


def count_valid_strings(len_str, operations):
    counter = 0
    for chars in itertools.product("abcdef", repeat=len_str):
        init_str = "".join(chars)
        if breadth_first_search(init_str, operations):
            counter += 1
    return counter


def main():
    n, q = list(map(int, input().split()))
    operations = [Operation(*input().split()) for _ in range(q)]
    print(count_valid_strings(n, operations))


def __starting_point():
    main()

__starting_point()

def search(rules, m):
    ret = ['a']
    for i in range(m - 1):
        nex = []
        for r in ret:
            r0, tail = r[0], r[1:]
            for a, b in rules:
                if a == r0:
                    nex.append(b + tail)
        ret = nex
    # print(ret)
    return len(ret)


def main():
    line = [int(i) for i in input().split()]
    m, n = line[0], line[1]
    rules = []
    for i in range(n):
        line = input().split()
        line.reverse()
        rules.append(line)
    # print(m)
    # print(rules)
    l = search(rules, m)
    print(l)


main()


n, m = list(map(int, input().split()))
d = {}
for i in range(m):
    t, o = input().split()
    if o in d:
        d[o].append(t)
    else:
        d[o] = [t]
    
q = [('a', 0)]
cnt = 0
while q and q[0][1] < n :
    st = q[0]
    q.pop(0)
    if st[1] == n - 1:
        cnt += 1
    if st[0][0] in d:
        for j in d[st[0][0]]:
            q.append((j + st[0][1:], st[1] + 1))
            
print(cnt)    


import collections

n, q = list(map(int, input().split()))
d = collections.defaultdict(list)
cnt, t = [0] * 6, [0] * 6
for i in range(q):
    s1, s2 = input().split()
    d[s2].append(s1)
    cnt[ord(s2) - ord('a')] += 1
for s in d['a']:
    t[ord(s[0]) - ord('a')] += 1
for i in range(n - 2):
    p = [0] * 6
    for j in range(6):
        if t[j] == 0:
            continue
        for s in d[chr(j + 97)]:
            p[ord(s[0]) - ord('a')] += t[j]
    t = p
print(sum(t))
    


n, m = list(map(int, input().split()))
t = [[] for i in range(6)]
for i in range(m):
    a, b = input().split()
    t[ord(b) - ord('a')] += [a]

l = ['a']
A = 0
while len(l) > 0:
    L = []
    for s in l:
        if len(s) == n:
            A += 1
            continue
        for i in range(1):
            ch = s[i]
            for new in t[ord(ch) - ord('a')]:
                L += [s[:i] + new + s[i+1:]]
    l = set(L)

print(A)
                


def __starting_point():
    n,m = list(map(int,input().split(' ')))
    d = {}
    depo,res = {},[]
    def bazinga(s):
        if s in depo:   return depo[s]
        if s[0] not in d:  depo[s]=0
        else:
            ans=0
            for aa in d[s[0]]:
                if len(aa+s[1:])==n:
                    ans+=1
                    #res.append(aa+s[1:])   #if problem is to find string
                elif len(aa+s[1:])>n:
                    continue
                else:
                    ans+=bazinga(aa+s[1:])
            depo[s]=ans
        return depo[s]

    for i in range(m):
        ai,bi = list(map(str,input().split(' ')))
        if bi in d:     d[bi] +=[ai]
        else:           d[bi]=[ai]
    print(bazinga('a'))
    #print(len(set(res)))

                    
                
                
                

'''
    A = input()
    stack = []      #Real Stack
    Graph = {
        ')':'('
        }
    count = 0
    def black(A):
        #p for possibility
        stak =[]
        for e in A:
            if e in ['(']:
                stak.append(e)
            else:
                if stak==[] or Graph[e]!=stak[-1]:
                    p=False
                else:
                    stak.pop(len(stak)-1)     #pop last 
        if len(stak) ==0:
            p=True
        else:
            p=False
        if not p:   return [0]
        else:
            #stak is not empty
            stak = []
            count = []
            for e in range(len(A)):
                if A[e]=='(' or stak==[]:  stak.append(A[e])
                else:
                    if A[e]==')' and Graph[A[e]]==stak[-1]:
                        while Graph[A[e]]==stak[-1]:
                            stak.pop(-1)
                            if e==len(A)-1: break
                            e+=1
                            if A[e]=='(' or stak==[]:   break
                        count.append(1)
            return count

    rov = []
    P = False 
    for e in A:
        if e in ['(']:  stack.append(e)
        else:
            if stack!=[]:
                stack.append(e)
                if stack.count('(')==stack.count(')'):
                    x=black(stack)
                    if x!=[0]:    P = True
                    if x==[1]:
                        rov.append(1)
                    else:
                        rov.append(sum(x[:-1]))
                    stack=[]
    if not P:   print(0)
    else:
        pro =1
        for i in rov:   pro*=i
        print(pro)
    
'''

__starting_point()

# You lost the game.
n, q = map(int, input().split())
L = [list(str(input()).split(" ")) for _ in range(q)]
A = [[] for _ in range(6)]
B = "abcdef"
for i in range(q):
    e = B.index(L[i][1])
    A[e]  = A[e] + [L[i][0]]
R = [1,0,0,0,0,0]
for i in range(1,n):
    K = [0,0,0,0,0,0]
    for j in range(6):
        for k in A[j]:
            e = B.index(k[0])
            K[e] += R[j]
    R = K[:]
print(sum(R))

def main():
    n, q = list(map(int, input().split()))
    d, nxt, f = {c: [] for c in "abcdef"}, {"a"}, ''.join
    for _ in range(q):
        a, b = input().split()
        d[b].append(a)
    for _ in range(n - 1):
        cur, nxt = nxt, set()
        for l in map(list, cur):
            for s in d[l[0]]:
                l[0] = s
                nxt.add(f(l))
    print(len(nxt))


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3

alphabet = list('abcdef')

def all_strs_gen(n):
    s = ['a'] * n
    for i in range(0, len(alphabet) ** n):
        yield ''.join(s)
        for j in range(0, n):
            if s[j] == alphabet[-1]:
                s[j] = alphabet[0]
            else:
                s[j] = chr(ord(s[j]) + 1)
                break

n, q = [int(x) for x in input().split()]
ops = {}
for i in range(0, q):
    op, s = input().split()
    ops[op] = s

def compress(s):
    while s[0:2] in ops:
        # print(s)
        s = ops[s[0:2]] + s[2:]
    # print(s)
    # print()
    return s

count = 0
for s in all_strs_gen(n):
    if 'a' == compress(s):
        count += 1

print(count)



3

ans = set()

def gen(cur, n, ops):
    if len(cur) == n:
        ans.add(cur)
    else:
        for t in ops[ord(cur[0]) - ord("a")]:
            gen(t + cur[1:], n, ops)


n, q = list(map(int, input().split()))
ops = [[] for i in range(6)]
for i in range(q):
    s, t = input().split()
    ops[ord(t[0]) - ord('a')].append(s)

gen("a", n, ops)
print(len(ans))


n,q = map(int,input().split())
ops = dict()
for _ in range(q):
	a,b = input().split()
	ops[a] = b
from itertools import product
count = 0
for t in product('abcdef', repeat=n):
	s = ''.join(t)
	while len(s) > 1:
		s = ops.get(s[:2], 'g') + s[2:]
	count += s == 'a'
print(count)

from collections import defaultdict

def rep(cand, succ):
    ret = set()
    for word in cand:
        for r in succ[word[0]]:
            ret.add(r + word[1:])

    return ret

n, q = list(map(int, input().split()))
succ = defaultdict(list)

for _ in range(q):
    a, b = input().split()
    succ[b].append(a)

cand = set("a")
for _ in range(n - 1):
    cand = rep(cand, succ)
print(len(cand))


n, q = (int(i) for i in input().split(' '))

oper = {}
for i in range(q):
	key, value = (i for i in input().split(' '))
	oper[key] = value


abc = ['a', 'b', 'c', 'd', 'e', 'f']

all_v = 0
n -= 2

def generate(mystr, num):
	nonlocal all_v
	#print('mystr="%s", num=%d'%(mystr, num))
	try:
		mystr = oper[mystr]
	except KeyError:
		return

	if num == 0:
		if mystr == 'a':
			all_v += 1
		return

	for a in abc:
		generate(mystr+a, num-1)

for key in oper.keys():
	generate(key, n)

print(all_v)

#/usr/bin/env pypy3
# -*- coding: utf-8 -*-

import collections
import itertools


GOAL = "a"
Operation = collections.namedtuple("Operation", "before after")


def is_possible_operation(original_str, operation):
    return original_str.startswith(operation.before)


def perform_operation(original_str, operation):
    return original_str.replace(operation.before, operation.after, 1)


def judge_dfs(initial_str, operations):
    stack = collections.deque()
    stack.append(initial_str)
    visited = collections.defaultdict(bool)
    visited[initial_str] = True
    while stack:
        original_str = stack.pop()
        if original_str == GOAL:
            return True
        for operation in operations:
            if is_possible_operation(original_str, operation):
                after_str = perform_operation(original_str, operation)
                if not visited[after_str]:
                    visited[after_str] = True
                    stack.append(after_str)
    else:
        return False


def count_valid_strings(len_init_str, operations):
    cands = itertools.product("abcdef", repeat=len_init_str)
    a = sum(1 for cs in cands if judge_dfs("".join(cs), operations))
    return a


def main():
    n, q = list(map(int, input().split()))
    operations = [Operation(*input().split()) for _ in range(q)]
    print(count_valid_strings(n, operations))


def __starting_point():
    main()

__starting_point()