#include <bits/stdc++.h>

template <typename T> inline void rd(T& x) {
	int si = 1; char c = getchar(); x = 0;
	while(!isdigit(c)) si = c == '-' ? -1 : si, c = getchar();
	while(isdigit(c)) x = x * 10 + c - 48, c = getchar();
	x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) { rd(x); rd(args...); }
#define fi first
#define se second
#define mkp std::make_pair
typedef long long ll;
typedef double ff;
typedef std::pair <int, int> pii;
const int kN = 3000 + 5, kInf = 0x3f3f3f3f;
const ll kMod = 998244353, kInfLL = 0x3f3f3f3f3f3f3f3fLL;

int n, k, A[kN][kN], fa[kN], siz[kN]; ll fac[kN];
int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
void Merge(int x, int y) {
	//printf("%d %d\n", x, y);
	int f_x = Find(x), f_y = Find(y);
	if(f_x == f_y) return;
	fa[f_x] = f_y; siz[f_y] += siz[f_x];
}

void Init() {
	fac[0] = 1;
	for(int i = 1; i <= n * 2; ++i) {
		fa[i] = i, siz[i] = 1;
		fac[i] = fac[i - 1] * i % kMod;
	}
}

int GetIdx(pii x) { return (x.fi - 1) * n + x.se; }

void Solve() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			bool flag = true;
			for(int p = 1; p <= n; ++p) 
				if(A[i][p] + A[j][p] > k) flag = false;
				//printf("%d\n", );
			if(flag) Merge(i, j);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			bool flag = true;
			for(int p = 1; p <= n; ++p) 
				if(A[p][i] + A[p][j] > k) flag = false;
			if(flag) Merge(i + n, j + n);
		}
	}
}

int main() { 
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int T = 1; //rd(T);
	while(T--) {
		rd(n, k); Init();
		for(int i = 1; i <= n; ++i) 
			for(int j = 1; j <= n; ++j) {
				rd(A[i][j]);
				//idx[(i - 1) * n + j] = mkp(i, j);
			}
		Solve();
		ll ans = 1;
		for(int i = 1; i <= n * n; ++i) if(fa[i] == i) {
			ans = ans * fac[siz[i]] % kMod;
		}
		printf("%lld\n", ans);
	} return 0;
}
#include "bits/stdc++.h"

using namespace std;

using str = string;
using db = double;

#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ist insert
#define ers erase

#define ppf pop_front()
#define ppb pop_back()
#define ft front()
#define bk back()
#define ety empty()
#define F first
#define S second

#define all(v) (v).begin(), (v).end()
#define srt(v) sort(all(v));
#define rev(v) reverse(all(v));

#define ice(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define fire(i, a, b) for (int (i) = (b) - 1; (i) >= (a); --(i))

template <class T>
inline int sz(T container) {
    return int(container.size());
}

template <class T>
bool ckmin(T& a, const T& b) { // a = min(a, b)
    return a > b ? a = b, 1 : 0;
}

template <class T>
bool ckmax(T& a, const T& b) { // a = max(a, b)
    return a < b ? a = b, 1 : 0;
}

template <class T>
void show(vector<T> v) {
    for (auto a : v) { cout << a << ' '; } cout << '\n';
}

template <class T>
void show2d(vector<vector<T>> v) {
    for (auto b : v) { for (auto a : b) { cout << a << ' '; } cout << '\n'; }
}

template <class T, class U>
void showPair(vector<pair<T, U>> v) {
    for (auto a : v) { cout << a.F << ' ' << a.S << '\n'; }
}

const long long MOD[3] = {1000000007, 998244353, 9223372036854775807};

template <class T>
T modpow(T base, T exp, T mod) {
    if (exp == 0) return 1 % mod;
    T ans = modpow(base, exp / 2, mod);
    ans *= ans; ans %= mod;
    if (exp & 1) { ans *= base; ans %= mod; }
    return ans;
}

vector<vector<tuple<int, long long, long long>>> adj(100000);
vector<long long> dis(100000, MOD[2]);
vector<bool> done(100000);
priority_queue<pair<long long, int>> q;

void solve() {
    int n, m; cin >> n >> m;
    ice (i, 0, m) {
        int a, b, c, d; cin >> a >> b >> c >> d; --a, --b;
        adj[a].eb(b, c, d); adj[b].eb(a, c, d);
    }
    dis[0] = 0;
    q.emplace(0, 0);
    while (!q.ety) {
        int cur = q.top().S; q.pop();
        if (done[cur]) continue;
        done[cur] = true;
        for (auto nxt : adj[cur]) {
            int to; long long C, D; tie(to, C, D) = nxt;
            auto until = (long long) floor(sqrt(double(D)));
            if (dis[cur] < until) {
                if (until + C + D / (until + 1) < dis[to]) {
                    dis[to] = until + C + D / (until + 1);
                    q.emplace(-dis[to], to);
                }
            } else {
                if (dis[cur] + C + D / (dis[cur] + 1) < dis[to]) {
                    dis[to] = dis[cur] + C + D / (dis[cur] + 1);
                    q.emplace(-dis[to], to);
                }
            }
        }
    }
    cout << (dis[n - 1] == MOD[2] ? -1 : dis[n - 1]);
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(17);
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
}