#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF (1<<30)
#define mod 104659

using namespace std;
int n, m, i, j, k, s, b, p[27][27], r[27][27], a[27][27];
char l[5];
int main()
{
    freopen("nrcuv.in", "r", stdin);
    freopen("nrcuv.out", "w", stdout);
    // O(m*m*m*log(n))
    scanf("%d%d\n", &n, &m);
    for(i=0;i<26;i++)
        for(j=0;j<26;j++)
            p[i][j]=1;
    while(m--)
    {
        gets(l+1);
        i=l[1]-'a';
        j=l[3]-'a';
        p[i][j]=p[j][i]=0;
    }
    for(i=0;i<26;i++)
        r[25][i]=1;
    n--;
    for(b=0;(1<<b)<=n;b++)
    {
        if((1<<b)&n)
        {
            for(i=0;i<26;i++)
                for(j=0;j<26;j++)
                    a[i][j]=0;
            for(i=0;i<26;i++)
                for(j=0;j<26;j++)
                    for(k=0;k<26;k++)
                    {
                        a[i][j]+=(1LL*r[i][k]*p[k][j])%mod;
                        if(a[i][j]>=mod) a[i][j]-=mod;
                    }
            for(i=0;i<26;i++)
                for(j=0;j<26;j++)
                    r[i][j]=a[i][j];
        }
        for(i=0;i<26;i++)
            for(j=0;j<26;j++)
                a[i][j]=0;
        for(i=0;i<26;i++)
            for(j=0;j<26;j++)
                for(k=0;k<26;k++)
                {
                    a[i][j]+=(1LL*p[i][k]*p[k][j])%mod;
                    if(a[i][j]>=mod) a[i][j]-=mod;
                }
        for(i=0;i<26;i++)
            for(j=0;j<26;j++)
                p[i][j]=a[i][j];
    }
    for(i=0;i<26;i++)
    {
        s+=r[25][i];
        if(s>=mod) s-=mod;
    }
    printf("%d", s);
    return 0;
}