#include <algorithm>
#include <iostream>
#include <climits>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

// ------------------------------------------------

template <typename T> istream &operator>>
(istream &is, vector<T> &vec) 
{   for (auto &v : vec) is >> v; return is; }

template<typename T> 
void dout(string name, T arg) {
    cerr << arg << endl;
}

template<typename T1, typename... T2> 
void dout(string names, T1 arg, T2... args) {
    cerr << arg << " | ";
    dout(names.substr(names.find(',') + 2), args...);
}

#ifndef ONLINE_JUDGE
    #define debug(...) dout(#__VA_ARGS__, __VA_ARGS__)
#else
    #define debug(...) 
#endif

// --------------------------------------------------

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define mod 1000000007
#define nod 1000000007
#define vi vector<int>
#define vll vector<ll>
#define pb push_back


// D R U L
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

const int mx = 1e6 + 5;
const int INF = mod;

ll power(ll x, ll y){
    ll res = 1;
    while(y > 0){
        if(y & 1) res = (res * x) % nod;
        y >>= 1;
        x = (x * x) % nod;
    }
    return (res % nod);
}



// Check for number of Cases!!
void solve() {
    ll n; cin >> n;
    ll cost; cin >> cost;
    
    vector<vll> arr(n, vll(n));
    cin >> arr;
    
    vll ref;
    
    for(int i = 1; i < n; i++) {
        ref.pb(i);
    }
    
    ll ans = 0;
    
    do {
        ll curr = 0;
        for(int i = 0; i < ref.size(); i++) {
            if(i == 0) {
                curr += arr[0][ref[i]];
            }else {
                curr += arr[ref[i-1]][ref[i]];
            }
        }
        curr += arr[ref[ref.size() - 1]][0];
        if(curr == cost) ans++;
    }while(next_permutation(all(ref)));
    
    
    cout << ans;
}

int main(){

    #ifndef ONLINE_JUDGE
    freopen("/ATOMCODES/input.txt", "r", stdin);
    freopen("/ATOMCODES/output.txt", "w", stdout);
    freopen("/ATOMCODES/err_output.txt", "w", stderr);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t;
    while(t--) {
      solve();
    }
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int N, M; cin >> N >> M;
    vector<int> X(M), Y(M), Z(M);
    rep(i, M){
        cin >> X[i] >> Y[i] >> Z[i];
    }

    ll dp[1<<18]{}; dp[0] = 1;
    for(int bit=0; bit<(1<<N); bit++){
        vector<int> S; //集合
        for(int i=0; i<N; i++){
            if((bit>>i)&1){
                S.push_back(i+1);
            }
        }
        for(int i=0; i<N; i++){
            if((bit>>i)&1)continue; //既に存在する
            S.push_back(i+1);
            bool fg = true;
            //条件判定
            rep(j, M){
                if(X[j]!=S.size())continue; //丁度になったら数えれば良い
                int cnt = 0;
                for(auto s:S){
                    if(s<=Y[j])cnt++;
                }
                if(cnt>Z[j]){
                    fg = false;
                }
            }
            if(fg)dp[bit+(1<<i)] += dp[bit];
            //cout << "bit:" << bit << " dp:" << dp[bit+(1<<i)] << " <- " << dp[bit] << ln;
            S.pop_back();
        }
    }
    cout << dp[(1<<N)-1] << ln;
}
