#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define Pr pair<ll,ll>
#define Tp tuple<ll,ll,ll>
using Graph = vector<vector<int>>;

ll mod = 1000000007;

int main() {
    ll N; cin >> N;
    ll dp[N+1][N+1];
    ll sum[N+1]; sum[0] = 0;
    rep(i,N){
        ll a; cin >> a;
        sum[i+1] = sum[i] + a;
    }
    rep(i,N+1){
        rep(j,N+1){
            dp[i][j] = 0;
        }
    }
    rep(i,N) dp[1][i+1] = 1;
    vector<int> prev;
    for(ll i=2;i<=N;i++){
        prev.assign(N+1,-1); prev[0] = 0;
        rep(j,N){
            ll k = sum[j+1]%i;
            if(prev[k]!=-1){
                dp[i][j+1] = dp[i][prev[k]] + dp[i-1][prev[k]];
                dp[i][j+1] %= mod;
            }
            prev[k] = j+1;
        }
    }
    ll ans = 0;
    rep(i,N+1){
        ans += dp[i][N]; ans %= mod;
    }
    cout << ans << endl;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <climits>
#define ll long long
#define mod 1000000007

// templates
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define po(x,y)   fixed<<setprecision(y)<<x
#define ss(s) scanf(" %[^\n]%*c", s)
#define sc(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define ps(s) printf("%s\n",s)
#define pr(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define prs(n) printf("%d ",n)
#define pls(n) printf("%lld ",n)
using namespace std;

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


ll calc(int p, int mask) {

	if (dp[p][mask] != -1)return dp[p][mask];

	ll ans = 0;
	for (auto x : v[p]) {

		int y = x.F, z = x.S;
		int rem = mask % (1 << y);
		int d = __builtin_popcount(rem);
		if (d > z) {

			return dp[p][mask] = 0;
		}
	}
	if (p == n) {
		return dp[p][mask] = 1;
	}
	for (int i = 0; i < n; i++) {

		if ((mask >> i) & 1)continue;
		ans += calc(p + 1, mask | (1 << i));

	}
	return dp[p][mask] = ans;
}

void solve()
{
	memset(dp, -1LL, sizeof(dp));
	sc(n), sc(m);
	for (int i = 0; i < m; ++i)
	{
		int x, y, z;
		sc(x), sc(y), sc(z);
		v[x].push_back({y, z});
	}

	pl(calc(0, 0));

}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int t = 1;
	// sc(t);
	while (t--) {
		solve();
	}
	// cerr<< (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
	return 0;

}