#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll, ll>;
const ll INF = ll(1e18);
const ll mod = ll(998244353);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rnfor(i,a,b) for(ll (i) = (b) - 1; (i) >= (a); --(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int multipf(vector<string>& s){
    cout << s[0];
    rep1(i, s.size() - 1)cout << " " << s[i];
    cout << endl;
    return 0;
}

int multipf(vector<ll>& n){
    cout << n[0];
    rep1(i, n.size() - 1)cout << " " << n[i];
    cout << endl;
    return 0;
}

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}
 
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b){
    ll ans = 1;
    while(b) {
        if(b & 1LL) ans = ans * a % mod;
        ans %= mod;
        a = a * a;
        a %= mod;
        b >>= 1;
    }
    return ans % mod;
}

struct seg {
    ll n;
    vector<ll> dat;
    seg(ll m) : n(), dat(m * 4, 0) {
        int x = 1;
        while (m > x) {
            x *= 2;
        }
        n = x;
    }
    void update(ll i, ll x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = dat[i * 2 + 1] ^ dat[i * 2 + 2];
        }
    }
    
    ll query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
    ll query_sub(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) {
            return 0;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            ll vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            ll vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return (vl ^ vr);
        }
    }
};

//modの値の確認をすること
int main(){
    ll n,ans = 1e10;
    string s;
    cin >> n >> s;
    if(n == 1 && s[0] == '1'){
        pf(ans * 2);
        return 0;
    }
    if(n == 2 && s[0] == '1' && s[1] == '1'){
        pf(ans);
        return 0;
    }
    ll c = INF,cnt = 0;
    rep0(i, n)if(s[i] == '0'){
        c = i;
        ++cnt;
        break;
    }
    if(c > 2){
        ans = 0;
    }else{
        nfor(i, c + 1, n){
            if(s[i] == '0'){
                if(i - c != 3){
                    ans = 0;
                }
                c = i;
                ++cnt;
            }
        }
    }
    if(ans == 0){
        pf(0);
    }else if(s[n - 1] == '1'){
        pf(ans - cnt);
    }else{
        pf(ans - cnt + 1);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7
#define INF LONG_MAX/3

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

vector<pair<ll, ll> > CON[20];

ll dp[20][272144];

int main(){
	ll N, M;
	cin >> N >> M;
	rep(i, M) {
		ll x, y, z;
		cin >> x >> y >> z;
		x--;y--;
		CON[x].push_back(make_pair(y, z));
	}

	dp[0][0] = 1;
	rep(i, N) {
		rep(mask, (1LL<<N)) {
			if(dp[i][mask] == 0) continue;
			rep(next, N) {
				if((mask>>next)&1) continue;
				ll nmask = mask | (1LL<<next);

				dp[i+1][nmask] += dp[i][mask];
			}
		}

		rep(mask, (1LL<<N)) {
			bool ng = false;

			for(auto item: CON[i]) {
				ll y = item.first;
				ll z = item.second;
				ll num = 0;
				rep(bit, y+1) if((mask>>bit)&1) num++;
				if(num > z) {
					ng = true;
					break;
				}
			}

			if(ng) dp[i+1][mask] = 0;
		}
	}

	ll ans = 0;
	rep(mask, (1LL<<N)) {
		ans += dp[N][mask];
	}
	cout << ans << endl;
}
