#include <bits/stdc++.h>

using namespace std;

#define closeSync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
const int LIM = 30;

map<pii,int> mp;
int n,m;
vector<int> G[MAXN][LIM];
struct Node{
    int u,v;
    int stp;
};
int vis[MAXN][MAXN];
int ans = INF;

inline void bfs(int st,int ed)
{
    queue<Node> q;
    q.push({st,ed,0});
    vis[st][ed] = vis[ed][st] = 1;
    while (!q.empty())
    {
        Node cur = q.front();
        q.pop();
        int u = cur.u,v = cur.v;
        if (mp.count({u,v}))
        {
            ans = min(ans,cur.stp+(u != v));
            continue;
        }
        for (int i=0;i<='z'-'a';i++)
        {
            for (auto uu : G[u][i])
            {
                for (auto vv : G[v][i])
                {
                    if (vis[uu][vv] == 0)
                    {
                        vis[uu][vv] = vis[vv][uu] = 1;
                        q.push({uu,vv,cur.stp+2});
                    }
                }
            }
        }
    }
}

inline void solve()
{
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        int u,v;char c;    cin >> u >> v >> c;
        G[u][c-'a'].push_back(v);
        G[v][c-'a'].push_back(u);
        mp[{u,v}] = mp[{v,u}] = 1;
    }
    for (int i=1;i<=n;i++)
        mp[{i,i}] = 1;

    bfs(1,n);
    cout << (ans==INF ? -1 : ans) << endl;

    return ;
}

int main()
{closeSync;
    // int T;  cin >> T;
    // while (T--)
        solve();
    return 0;
}
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
template<typename T>void ckmn(T&a,T b){a=min(a,b);}
template<typename T>void ckmx(T&a,T b){a=max(a,b);}
void rd(int&x){scanf("%i",&x);}
void rd(ll&x){scanf("%lld",&x);}
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;}
int ri(){int x;rd(x);return x;}
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;}
template<typename T>void ra(T a[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]);}
template<typename T1,typename T2>void ra(T1 a[],T2 b[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]);}
template<typename T1,typename T2,typename T3>void ra(T1 a[],T2 b[],T3 c[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]),rd(c[st+i]);}
void re(vector<int> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){rd(u,v);E[u].pb(v);if(!dir)E[v].pb(u);}}
template<typename T>void re(vector<pair<int,T>> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){T w;rd(u,v,w);E[u].pb({v,w});if(!dir)E[v].pb({u,w});}}

const int mod=1e9+7;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
void ckadd(int&a,int b){a=add(a,b);}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
void cksub(int&a,int b){a=sub(a,b);}
int mul(int a,int b){return (ll)a*b%mod;}
void ckmul(int&a,int b){a=mul(a,b);}
int powmod(int x,int k){int ans=1;for(;k;k>>=1,ckmul(x,x))if(k&1)ckmul(ans,x);return ans;}
int inv(int x){return powmod(x,mod-2);}

const int N=10050;
int F[N],I[N];
int binom(int n, int k){ return mul(F[n],mul(I[k],I[n-k]));}
void calc()
{
	F[0]=1;
	for(int i=1;i<N;i++) F[i]=mul(F[i-1],i);
	I[N-1]=inv(F[N-1]);
	for(int i=N-2;~i;i--) I[i]=mul(I[i+1],i+1);
}

int main(){
	int n=ri();
	calc();
	char AA,AB,BA,BB;
	scanf("\n%c",&AA);
	scanf("\n%c",&AB);
	scanf("\n%c",&BA);
	scanf("\n%c",&BB);
	if(n<=3)return 0*printf("1\n");
	if(AA=='A'&&BB=='B')return 0*printf("1\n");
	if(AA=='B'&&BB=='A'){
		if(AB!=BA)return 0*printf("%i\n",powmod(2,n-3));
		int ans=0;
		for(int ba=0;ba*2<=n-2;ba++){
			int a=n-2-ba*2;
			ckadd(ans,binom(ba+a,a));
		}
		printf("%i\n",ans);
		return 0;
	}
	if(AA=='A'){
		AA='B';
		AB=AB=='A'?'B':'A';
		BA=BA=='A'?'B':'A';
		BB='B';
		//swap(AB,BA);
	}
	//AA -> ABA
	//BB -> BBB
	if(AB=='B'){
		//AB -> ABB
		printf("1\n");
		return 0;
	}else{
		//AB -> AAB
		if(BA=='A'){
			//BA -> BAA
			int ans=0;
			for(int ba=0;ba*2<=n-2;ba++){
				int a=n-2-ba*2;
				ckadd(ans,binom(ba+a,a));
			}
			printf("%i\n",ans);
			return 0;
		}else{
			//BA -> BBA
			int ans=powmod(2,n-3);
			printf("%i\n",ans);
			return 0;
		}
	}
	return 0;
}