program mire;
const mo=104659;

var f,g:text;
    n,m:integer;
    a:array[0..27,0..27] of 0..1;
    s:array[-1..1001, -1..27] of longint;
procedure citire;
var i:integer;
     x,z,y:char;
begin
  assign(f,'nrcuv.in'); reset(f);
  assign(g,'nrcuv.out'); rewrite(g);
   readln(f,n,m);
   for i:=1 to m do
     begin
        readln(f,x,z,y);
        a[ord(x)-96,ord(y)-96]:=1;
        a[ord(y)-96,ord(x)-96]:=1;
     end;
  close(f);
end;
procedure dinamica;
var i,j,k:integer;
      su:longint;
begin
 //s[i,j]= nr de cuv de lungime i ce pot fii formate avand ultima litera j
 // s[i,j]=sum(a[i-1,k]) k=1,n cu prop. ca pot forma perechea (k,j) sau (j,k)
 for i:=0 to 26 do
   s[1,i]:=1;
 for i:=2 to n do
   for j:=1 to 26 do
       for k:=1 to 26 do
         if (a[j,k]=0) then
            s[i,j]:=(s[i,j]+s[i-1,k]) mod mo;
 {for i:=1 to n do
   begin
      for j:=1 to 26 do
        write(s[i,j],' ');
      writeln;
   end; }
   su:=0;
   for i:=1 to 26 do
     su:=(su+s[n,i]) mod mo;
 writeln(g,su mod mo);
 close(g);
end;
begin
 citire;
 dinamica;
end.