#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

vector<vector<int>> graph;
vector<vector<bool>> isReach;
int n,m;
void init() {
  for (int i = 0; i < n; ++i)
  {
    isReach[i][i] = true;
    queue<int> nxt;
    nxt.push(i);
    vector<bool> seen(n, false);
    while (!nxt.empty()) {
      auto now = nxt.front();
      nxt.pop();
      seen[now] = true;
      isReach[i][now] = true;
      for (const auto& e: graph[now]) {
        if (seen[e]) continue;
        nxt.push(e);
      }
    }
  }
}


int main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cin>>n>>m;
  graph.resize(n);
  for (int i = 0; i < m; ++i)
  {
    int a,b;
    cin>>a>>b;
    a--; b--;
    graph[a].push_back(b);
  }
  int ans = 0;
  isReach = vector<vector<bool>>(n, vector<bool>(n, false));
  init();
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      if (isReach[i][j]) ans++;
    }
  }
  cout << ans << "\n";
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    int n, k;
    cin >> n >> k;
    vvec<int> t(n, vec<int>(n, 0));
    rep(i, n) rep(j, n) cin >> t[i][j];
    int array[n-1];
    rep(i, n-1) array[i] = i + 1;
    int prev, cost, ans;
    ans = 0;
    do{
        prev = 0;
        cost = 0;
        // for(int i=0; i<n-1; i++){
        //     cout<<array[i];
        //     if(i!=3)cout<<" ";
        // }
        // cout<<endl;
        for(int i=0; i<n-1; i++){
            cost += t[prev][array[i]];
            prev = array[i];
        }
        cost += t[prev][0];
        if (cost == k) ans++;
    } while (next_permutation(array,array+n-1));
    cout << ans << endl;
}