#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
constexpr ll MOD=998244353;
constexpr ll INF=2e18;

VVI g(300000);
VI in(300000,0);
VI ans(300000,0);
VI kk(300000,0);

void dfs(int v){
    for(auto to:g[v]){
        ans[to]+=ans[v];
        if(--in[to]==0){
            dfs(to);
        }
    }
}

int main(){
    int n, m; cin >> n >> m;
    VVI c(n+1,VI(n+1,INF));
    int x, y, z;
    REP(i,m){
        cin >> x >> y >> z;
        for(int j=x;j>=0;j--)
            c[j][y]=min(c[j][y],(ll)z);
        for(int k=y;k>=0;k--)
            c[x][k]=min(c[x][k],(ll)z);
    }
    REP(i,1<<n){
        int popc=0, cnt=0;
        bool no=0;
        REP(j,n){
            if(i>>j&1)
                popc++;
        }
        REP(j,n){
            if(i>>j&1)
                cnt++;
            if(c[popc][j+1]<cnt){
                no=1;
                break;
            }
        }
        if(!no)
            kk[i]=1;
    }
    kk[0]++;
    REP(i,1<<n){
        if(kk[i]==2){
            REP(j,n){
                if(!(i>>j&1)){
                    if(kk[i|(1<<j)]){
                        kk[i|(1<<j)]=2;
                        g[i].push_back(i|(1<<j));
                        in[i|(1<<j)]++;
                    }
                }
            }
        }
    }
    ans[0]=1;
    dfs(0);
    cout << ans[(1<<n)-1] << endl;
    return 0;
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,mod=1e9+7;
int n,f[N];
char AA,AB,BA,BB;
int qp(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>AA>>AB>>BA>>BB;
	if(n==2)
	{
		cout<<1<<endl;
		return 0;
	}
	if(AB=='A')
	{
		if(AA=='A')
		{
			cout<<1<<endl;
			return 0;
		}
		if(BA=='A')
		{
			f[0]=1,f[1]=2;
			for(int i=2;i<=n;i++)
				f[i]=(f[i-1]+f[i-2])%mod;
			cout<<f[n-3]<<endl;
			return 0;
		}
		cout<<qp(2,n-3)<<endl;
	}
	else
	{
		if(BB=='B')
		{
			cout<<1<<endl;
			return 0;
		}
		if(BA=='B')
		{
			f[0]=1,f[1]=2;
			for(int i=2;i<=n;i++)
				f[i]=(f[i-1]+f[i-2])%mod;
			cout<<f[n-3]<<endl;
			return 0;
		}
		cout<<qp(2,n-3)<<endl;
	}
	return 0;
}