#include <bits/stdc++.h>

using namespace std;

int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	int n, k;
	cin >> n >> k;
	int t[n][n];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> t[i][j];
	}
	vector<int> p(n);
	for (int i = 0; i < n; i++)
		p[i] = i;
	int ans = 0;
	do
	{
		int cur = 0;
		for (int i = 0; i < n - 1; i++)
			cur += t[p[i]][p[i + 1]];
		cur += t[p[n - 1]][0];
		if (cur == k)
			ans++;
	} while (next_permutation(p.begin() + 1, p.end()));
	cout << ans;
	return 0;
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
typedef long long ll;
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> X(N + 1);
    rep(i, M) {
        int x, y, z;
        cin >> x >> y >> z;
        X[x].push_back({y, z});
    }

    int n = 1 << N;
    vector<ll> dp(n);
    dp[0] = 1;
    vector<int> mask(N + 1);
    rep(i, N) mask[i + 1] = mask[i] << 1 | 1;
    rep(s, n) {
        int cnt = __builtin_popcount(s);

        for (auto p : X[cnt]) {
            if (__builtin_popcount(s & mask[p.first]) > p.second) dp[s] = 0;
        }

        rep(j, N) {
            if (~s >> j & 1) dp[s | 1 << j] += dp[s];
        }
    }

    cout << dp[n - 1] << endl;

    return 0;
}