#include<bits/stdc++.h>

#define AynVul int main()
#define ll long long
#define task "A"
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define eb emplace_back
#define debug(a) cout << a << ' '
#define Debug(a, b) cout << a << ' ' << b << '\n'

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int Sz = 2e3+3;
const ll  MOD = 1e9+7;
const int oo = 1e9;

vi g[Sz];
vector<bool> vis(Sz);
int cnt[Sz];

int dfs(int u)
{
    int ans = 1;
    vis[u] = 1;
    for(int v: g[u])
        if(!vis[v])
            ans += dfs(v);

    return ans;
}

AynVul
{
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0);
    //~This too, shall pass~
    //Fighting

    int n, m;
    cin >> n >> m;

    rep(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
    }

    rep(i, 1, n) vis[i] = 0;

    int ans = 0;
    rep(i, 1, n)
    {
        vis.assign(n, 0);
        ans += dfs(i);
    }

    cout << ans;
    return 0;
}




#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define all(v) v.begin(),v.end()

const int mod = 1e9 + 7;
ll dp[(1 << 18)][18];
int main (){
    fast_io;
    ll n, m;
    cin >> n >> m;
    vector<vector<int> > constraints;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        constraints.push_back({x, y, z});
    }
    dp[0][0] = 1;
    for (int i = 0; i < (1 << n); i++) {
        int pref[n];
        memset(pref, 0, sizeof(pref));
        for (int j = 0; j < n; j++) {
            if (i & (1 << j))
                pref[j]++;
        }
        for (int j = 1; j < n; j++)
            pref[j] += pref[j - 1];
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == 0)
                continue;
            for (int k = 0; k < n; k++) {
                if ((i & (1 << k)))
                    continue;
                bool flag = false;
                int len = __builtin_popcount(i);
                for (auto& constraint: constraints) {
                    if (len != constraint[0])
                        continue;
                    if ((k <= constraint[1] && constraint[2] == pref[constraint[1]]) ||
                       (constraint[2] < pref[constraint[1]])) {
                        flag = true;
                        break;
                    }
                }
                if (flag == true)
                    continue;
                dp[i | (1 << k)][k] += dp[i][j];
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += dp[(1 << n) - 1][i];
    }
    cout << ans << endl;
}
