#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 55

#define P 100000000000000000LL

unsigned long long C[N][N];

int n,m,p[N*N*N],t=,tmp[];

int dfn[N*N*N],low[N*N*N],stk[N*N*N],SET[N*N*N],top=,cnt=;

bool flag[N*N*N];

char s[N],s2[N];

vector<int> ele[N*N*N];

struct magic{int n,a,b,c,x,y,z;}a[N<<];

struct data{int to,nxt;}edge[N*N*N*N];

struct biginteger

{

    unsigned long long x,y;

    bool operator <(const biginteger&a) const

    {

        return x==a.x?y<a.y:x<a.x;

    }

    bool operator >(const biginteger&a) const

    {

        return x==a.x?y>a.y:x>a.x;

    }

    biginteger operator +(const biginteger&a) const

    {

        biginteger v=(biginteger){x,y};

        v.x+=a.x;v.y+=a.y;

        if (v.y>=P) v.x++,v.y-=P;

        return v;

    }

    biginteger operator *(const unsigned long long&a) const

    {

        unsigned long long v[]={};int n=;

        biginteger tmp=(biginteger){x,y};

        while (tmp.y) v[++n]=tmp.y%,tmp.y/=;

        if (tmp.x)

        {

            n=;

            while (tmp.x) v[++n]=tmp.x%,tmp.x/=;

        }

        for (int i=;i<=n;i++) v[i]=v[i]*a;

        for (int i=;i<=n;i++)

        v[i+]+=v[i]/,v[i]%=;

        while (v[n+]) n++,v[n+]+=v[n]/,v[n]%=;

        for (int i=;i>=;i--) tmp.y=tmp.y*+v[i];

        for (int i=n;i>=;i--) tmp.x=tmp.x*+v[i];

        return tmp;

    }

}value[N*N*N],V[N*N*N],f[N*N*N];

int trans(int x,int y,int z){return x*(n+)*(n+)+y*(n+)+z+;}

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void tarjan(int k)

{

    dfn[k]=low[k]=++cnt;

    flag[k]=;stk[++top]=k;

    for (int i=p[k];i;i=edge[i].nxt)

    if (!dfn[edge[i].to]) tarjan(edge[i].to),low[k]=min(low[k],low[edge[i].to]);

    else if (flag[edge[i].to]) low[k]=min(low[k],dfn[edge[i].to]);

    if (dfn[k]==low[k])

    {

        t++;

        while (stk[top]!=k)

        {

            SET[stk[top]]=t;

            ele[t].push_back(stk[top]);

            V[t]=V[t]+value[stk[top]];

            flag[stk[top]]=;

            top--;

        }

        SET[k]=t;ele[t].push_back(k);V[t]=V[t]+value[k];flag[k]=;top--;

    }

}

namespace newgraph

{

    int n,t=,p[N*N*N]={},degree[N*N*N],q[N*N*N];

    struct data{int to,nxt;}edge[N*N*N*N];

    void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

    void topsort()

    {

        int head=,tail=;for (int i=;i<=n;i++) if (!degree[i]) q[++tail]=i;

        while (tail<n)

        {

            int x=q[++head];

            for (int i=p[x];i;i=edge[i].nxt)

            {

                degree[edge[i].to]--;

                if (!degree[edge[i].to]) q[++tail]=edge[i].to;

            }

        }

    }

    void solve()

    {

        topsort();

        for (int i=n;i>=;i--)

        {

            for (int j=p[q[i]];j;j=edge[j].nxt)

            f[q[i]]=max(f[q[i]],f[edge[j].to]);

            f[q[i]]=f[q[i]]+V[q[i]];

        }

    }

}

void rebuild()

{

    memset(flag,,sizeof(flag));

    for (int i=;i<=t;i++)

    {

        for (int j=;j<ele[i].size();j++)

            for (int k=p[ele[i][j]];k;k=edge[k].nxt)

            if (!flag[edge[k].to]&&SET[edge[k].to]!=i)

            {

                flag[edge[k].to]=;

                newgraph::addedge(i,SET[edge[k].to]);

                newgraph::degree[SET[edge[k].to]]++;

            }

        for (int j=;j<ele[i].size();j++)

            for (int k=p[ele[i][j]];k;k=edge[k].nxt)

            flag[edge[k].to]=;

    }

    newgraph::n=t;

}

int main()

{

    n=read(),m=read();

    for (int i=;i<=m;i++)

    {

        scanf("%s",s+);scanf("%s",s2+);

        a[i].n=strlen(s+);

        for (int j=;j<=a[i].n;j++)

        if (s[j]=='A') a[i].a++;

        else if (s[j]=='B') a[i].b++;

        else if (s[j]=='C') a[i].c++;

        for (int j=;j<=a[i].n;j++)

        if (s2[j]=='A') a[i].x++;

        else if (s2[j]=='B') a[i].y++;

        else if (s2[j]=='C') a[i].z++;

        if (a[i].a==a[i].x&&a[i].b==a[i].y&&a[i].c==a[i].z) a[i].a=a[i].b=a[i].c=n+;

    }

    C[][]=;

    for (int i=;i<=n;i++)

    {

        C[i][]=C[i][i]=;

        for (int j=;j<i;j++)

        C[i][j]=C[i-][j-]+C[i-][j];

    }

    for (int i=;i<=n;i++)

        for (int j=;j<=n-i;j++)

            for (int k=;k<=n-i-j;k++)

            {

                value[trans(i,j,k)]=(biginteger){,C[n][i]};

                value[trans(i,j,k)]=value[trans(i,j,k)]*C[n-i][j];

                value[trans(i,j,k)]=value[trans(i,j,k)]*C[n-i-j][k];

                for (int x=;x<=m;x++)

                if (i>=a[x].a&&j>=a[x].b&&k>=a[x].c&&n-i-j-k>=a[x].n-a[x].a-a[x].b-a[x].c)

                addedge(trans(i,j,k),trans(i-a[x].a+a[x].x,j-a[x].b+a[x].y,k-a[x].c+a[x].z));

            }

    t=;

    for (int i=;i<=n;i++)

        for (int j=;j<=n-i;j++)

            for (int k=;k<=n-i-j;k++)

            if (!dfn[trans(i,j,k)]) tarjan(trans(i,j,k));

    rebuild();

    newgraph::solve();

    biginteger ans=(biginteger){,};

    for (int i=;i<=t;i++) ans=max(ans,f[i]);

    if (ans.x)

    {

        cout<<ans.x;

        int x=;

        while (ans.y) tmp[++x]=ans.y%,ans.y/=;

        for (int i=;i>=;i--) cout<<tmp[i];

    }

    else cout<<ans.y;

    return ;

}