#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
const int maxn = 2000 + 5;
int fac[maxn];
int ifac[maxn];
int n;
int dp[maxn][maxn];
int calc(int n, int m) {
  if (!n) return !m;
  int& res = dp[n][m];
  if (~res) return res;
  res = 0;
  if (n > m) {
    int coef = mult(n - m, n - m);
    addmod(res, mult(coef, calc(n - 1, m)));
  }
  if (m >= 2) {
    int coef = mult(m, m - 1);
    addmod(res, mult(coef, calc(n - 1, m - 2)));
  }
  if (n > m && m) {
    int coef = mult(n - m, m);
    addmod(res, mult(coef, calc(n - 1, m - 1)));
    addmod(res, mult(coef, calc(n - 1, m - 1)));
  }
  return res;
}
int fen[2][maxn];
void upd(int fen[], int p, int val) {
  p++;
  for (; p < maxn; p += p & -p) {
    fen[p] += val;
  }
}
int query(int fen[], int p) {
  p++;
  int res = 0;
  for (; p > 0; p -= p & -p) {
    res += fen[p];
  }
  return res;
}
void chemthan() {
  fac[0] = 1;
  for (int i = (1); i < (maxn); ++i) fac[i] = mult(fac[i - 1], i);
  for (int i = (0); i < (maxn); ++i) ifac[i] = inv(fac[i]);
  memset(dp, -1, sizeof(dp));
  cin >> n;
  vector<vector<int> > a(n, vector<int>(n));
  for (int i = (0); i < (n); ++i) {
    for (int& x : a[i]) cin >> x, x--;
  }
  if (n == 1) {
    cout << 0 << "\n";
    return;
  }
  static int p[maxn];
  int x = mult(calc(n, n), ifac[n]);
  p[0] = 1;
  for (int i = (1); i < (maxn); ++i) p[i] = mult(p[i - 1], x);
  int res = 0;
  for (int i = (0); i < (n); ++i) {
    if (!i) {
      int coef = 0;
      static int f[maxn];
      memset(f, 0, sizeof(f));
      for (int t = (0); t < (n - 1); ++t) {
        int tot = 0;
        for (int j = (0); j < (n); ++j)
          if (j < a[i][t] && !f[j]) {
            tot++;
          }
        f[a[i][t]] = 1;
        addmod(coef, mult(tot, fac[n - t - 1]));
      }
      addmod(res, mult(coef, p[n - i - 1]));
    } else {
      static int f[maxn];
      static int g[maxn];
      memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)),
          memset(fen, 0, sizeof(fen));
      int num = 0;
      for (int t = (n)-1; t >= (0); --t) {
        int x = a[i][t];
        int y = a[i - 1][t];
        num += f[x] + g[y];
        f[y] = g[x] = 1;
        upd(fen[0], x, 1);
        if (f[x]) {
          upd(fen[1], x, 1);
        }
        if (g[y]) {
          upd(fen[1], y, 1);
        }
        int u = query(fen[0], x - 1);
        int v = query(fen[1], x - 1);
        assert(v <= u);
        if (t < n - 1) {
          int nnum = num;
          int nv = v;
          if (g[y]) {
            assert(nnum);
            nnum--;
          }
          if (g[y] && y < x) {
            assert(nv);
            nv--;
          }
          if (nnum && nv) {
            int coef = mult(calc(n - t - 1, nnum - 1), ifac[n - t - 1]);
            addmod(res, mult(nv, mult(p[n - i - 1], coef)));
          }
          int coef = mult(calc(n - t - 1, nnum), ifac[n - t - 1]);
          addmod(res, mult(u - v, mult(p[n - i - 1], coef)));
        }
      }
    }
  }
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

Petya collects beautiful matrix.

A matrix of size n × n is beautiful if: 

  * All elements of the matrix are integers between 1 and n; 
  * For every row of the matrix, all elements of this row are different; 
  * For every pair of vertically adjacent elements, these elements are different. 



Today Petya bought a beautiful matrix a of size n × n, and now he wants to determine its rarity.

The rarity of the matrix is its index in the list of beautiful matrices of size n × n, sorted in lexicographical order. Matrix comparison is done row by row. (The index of lexicographically smallest matrix is zero).

Since the number of beautiful matrices may be huge, Petya wants you to calculate the rarity of the matrix a modulo 998 244 353.

Input

The first line contains one integer n (1 ≤ n ≤ 2000) — the number of rows and columns in a.

Each of the next n lines contains n integers a_{i,j} (1 ≤ a_{i,j} ≤ n) — the elements of a.

It is guaranteed that a is a beautiful matrix.

Output

Print one integer — the rarity of matrix a, taken modulo 998 244 353.

Examples

Input


2
2 1
1 2


Output


1


Input


3
1 2 3
2 3 1
3 1 2


Output


1


Input


3
1 2 3
3 1 2
2 3 1


Output


3

Note

There are only 2 beautiful matrices of size 2 × 2:

<image>

There are the first 5 beautiful matrices of size 3 × 3 in lexicographical order:

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
const int maxn = 2000 + 5;
int fac[maxn];
int ifac[maxn];
int n;
int dp[maxn][maxn];
int calc(int n, int m) {
  if (!n) return !m;
  int& res = dp[n][m];
  if (~res) return res;
  res = 0;
  if (n > m) {
    int coef = mult(n - m, n - m);
    addmod(res, mult(coef, calc(n - 1, m)));
  }
  if (m >= 2) {
    int coef = mult(m, m - 1);
    addmod(res, mult(coef, calc(n - 1, m - 2)));
  }
  if (n > m && m) {
    int coef = mult(n - m, m);
    addmod(res, mult(coef, calc(n - 1, m - 1)));
    addmod(res, mult(coef, calc(n - 1, m - 1)));
  }
  return res;
}
int fen[2][maxn];
void upd(int fen[], int p, int val) {
  p++;
  for (; p < maxn; p += p & -p) {
    fen[p] += val;
  }
}
int query(int fen[], int p) {
  p++;
  int res = 0;
  for (; p > 0; p -= p & -p) {
    res += fen[p];
  }
  return res;
}
void chemthan() {
  fac[0] = 1;
  for (int i = (1); i < (maxn); ++i) fac[i] = mult(fac[i - 1], i);
  for (int i = (0); i < (maxn); ++i) ifac[i] = inv(fac[i]);
  memset(dp, -1, sizeof(dp));
  cin >> n;
  vector<vector<int> > a(n, vector<int>(n));
  for (int i = (0); i < (n); ++i) {
    for (int& x : a[i]) cin >> x, x--;
  }
  if (n == 1) {
    cout << 0 << "\n";
    return;
  }
  static int p[maxn];
  int x = mult(calc(n, n), ifac[n]);
  p[0] = 1;
  for (int i = (1); i < (maxn); ++i) p[i] = mult(p[i - 1], x);
  int res = 0;
  for (int i = (0); i < (n); ++i) {
    if (!i) {
      int coef = 0;
      static int f[maxn];
      memset(f, 0, sizeof(f));
      for (int t = (0); t < (n - 1); ++t) {
        int tot = 0;
        for (int j = (0); j < (n); ++j)
          if (j < a[i][t] && !f[j]) {
            tot++;
          }
        f[a[i][t]] = 1;
        addmod(coef, mult(tot, fac[n - t - 1]));
      }
      addmod(res, mult(coef, p[n - i - 1]));
    } else {
      static int f[maxn];
      static int g[maxn];
      memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)),
          memset(fen, 0, sizeof(fen));
      int num = 0;
      for (int t = (n)-1; t >= (0); --t) {
        int x = a[i][t];
        int y = a[i - 1][t];
        num += f[x] + g[y];
        f[y] = g[x] = 1;
        upd(fen[0], x, 1);
        if (f[x]) {
          upd(fen[1], x, 1);
        }
        if (g[y]) {
          upd(fen[1], y, 1);
        }
        int u = query(fen[0], x - 1);
        int v = query(fen[1], x - 1);
        assert(v <= u);
        if (t < n - 1) {
          int nnum = num;
          int nv = v;
          if (g[y]) {
            assert(nnum);
            nnum--;
          }
          if (g[y] && y < x) {
            assert(nv);
            nv--;
          }
          if (nnum && nv) {
            int coef = mult(calc(n - t - 1, nnum - 1), ifac[n - t - 1]);
            addmod(res, mult(nv, mult(p[n - i - 1], coef)));
          }
          int coef = mult(calc(n - t - 1, nnum), ifac[n - t - 1]);
          addmod(res, mult(u - v, mult(p[n - i - 1], coef)));
        }
      }
    }
  }
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```