s='АБВГД БВЕ ВЖГ ГДЖ ДЖЗ ЕВЖИ ЖИ ЗЖИ ИКЛ КМ ЛКМ'  
 d ={c[0]:c[1:] for c in s.split()}  
 k=0 
 def f(s,end): 
     global k 
     if s[-1]==end: 
       if len(s)<7: 
           k+=1 
       return 1 
     return sum(f(s+c,end)for c in d[s[-1]]) 
 print(f('А','М')-k) 
 

 
 s='АБВГД БВЕ ВЖГ ГДЖ ДЖЗ ЕВЖИ ЖИ ЗЖИ ИКЛ КМ ЛКМ'  
 d ={c[0]:c[1:] for c in s.split()}  
 def f(s,end): 
     if s[-1]==end: 
       if len(s)<7: 
           print(s) 
       return 1 
     return sum(f(s+c,end)for c in d[s[-1]]) 
 print(f('А','М')) 
  
 АБЕИКМ 
 АБЕИЛМ 
 АВЖИКМ 
 АВЖИЛМ 
 АГЖИКМ 
 АГЖИЛМ 
 АДЖИКМ 
 АДЖИЛМ 
 АДЗИКМ 
 АДЗИЛМ 
 

 
 G = {} 
 G['А'] = ["Б", "В", "Г", "Д"] 
 G['Б'] = ["В", "Е"] 
 G['В'] = ["Г", "Ж"] 
 G['Г'] = ["Д", "Ж"] 
 G['Д'] = ["Ж", "З"] 
 G['Е'] = ["В", "Ж", "И"] 
 G['Ж'] = ["И"] 
 G['З'] = ["Ж", "И"] 
 G['И'] = ["К", "Л"] 
 G['К'] = ["М"] 
 G['Л'] = ["К", "М"] 
  
 def valid(way): 
   return len(way) >= 7 
  
 count = 0 
 def allWays( fro, to, prev ): 
   global count 
   if fro == to: 
     if valid(prev): 
       print( prev ) 
       count += 1 
     return 
   for c in G[fro]: 
     if not c in prev: 
       allWays( c, to, prev+c ) 
  
 allWays( "А", "М", "A" ) 
 print( count )