#include <bits/stdc++.h>
using namespace std;

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)

#define fi first
#define se second

const int N = 19;
vector<pair<int,int>> ct[N];
ll dp[N][(1<<N)+10];
ll n, m;

bool ok(int mask, int i){
	for(auto &[tam,ns] : ct[i]){
		if(bitset<32>( ((1<<tam)-1)&(mask)).count()<ns) return 0;
	}
	return 1;
}

ll rec(int id, int mask){
	if(id==n) return 1;
	ll &ans = dp[id][mask];
	if(~ans) return ans;
	ans = 0;
	fr(i,n){
		if((mask&(1<<i))==0){
			int nmask = mask|(1<<i);
			if(ok(nmask,id)) ans+=rec(id+1,nmask);
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	 cin >> n >> m;
	fr(mm,m){
		ll xi, yi, zi; cin >> xi >> yi >> zi;
		yi = (n+1)-yi;
		yi--;
		yi--;
		
		ll need_smaller = max(0ll,xi-zi);
		if(need_smaller) ct[yi].emplace_back(xi,need_smaller);
	}		
	
	memset(dp,-1,sizeof(dp));
	cout << rec(0,0) << "\n";
}
#include <iostream>
#include <cstdio>
#define N 5005
using namespace std;

int n, c, c1[N], c2[N];
string a;
int main()
{
    int i, j;
    cin >> n >> a;
    a = '.' + a;
    for (i = 1; i <= n; i++) {
        c1[i] = c1[i - 1];
        c2[i] = c2[i - 1];
        if (a[i] == 'A') c1[i]++;
        else if (a[i] == 'C') c2[i]++;
        else if (a[i] == 'G') c2[i]--;
        else c1[i]--;
    }
    for (i = 1; i <= n; i++) {
        for (j = 0; j < i; j++) {
            if (c1[i] - c1[j] == 0 && c2[i] - c2[j] == 0) {
                c++;
            }
        }
    }
    cout << c << endl;
    return 0;
}