#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
struct tree_array {
  int num[2050], n, bigwei;
  void init(int nn = 2000) {
    n = nn;
    while (lowb(nn) != nn) nn -= lowb(nn);
    bigwei = nn;
    n = bigwei * 2;
    for (int i = 0; i < n; i++) num[i] = 0;
  }
  void upd(int no, int add) {
    while (no <= n) {
      num[no] += add;
      no += lowb(no);
    }
  }
  int que(int no) {
    int ans = 0;
    while (no) {
      ans += num[no];
      no -= lowb(no);
    }
    return ans;
  }
} all, matched;
const int maxn = 2010;
const int mod = 998244353;
int dp[maxn];
long long fac[maxn], invfac[maxn];
int orig[maxn][maxn], rep[maxn], have[2][maxn];
long long num_per[maxn][maxn];
int n;
long long c(int a, int b) {
  if (a < b) return 0;
  return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) scanf("%d", orig[i] + j);
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  invfac[n] = pow(fac[n], mod - 2, mod);
  for (int i = n - 1; i >= 0; i--) {
    invfac[i] = invfac[i + 1] * (i + 1) % mod;
  }
  num_per[1][0] = 1;
  num_per[1][1] = 0;
  for (int i = 2; i <= n; i++) {
    num_per[i][0] = fac[i];
    for (int j = 1; j <= i; j++) {
      num_per[i][j] = num_per[i][j - 1] - num_per[i - 1][j - 1];
      if (num_per[i][j] < 0) num_per[i][j] += mod;
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    all.init();
    matched.init();
    long long rk = 0;
    if (i > 0) {
      memset(have, 0, sizeof(have));
      for (int j = n - 1; j >= 0; j--) {
        rep[j] = rep[j + 1];
        long long small = all.que(orig[i][j]);
        long long rm = matched.que(orig[i][j]);
        all.upd(orig[i][j], 1);
        if (have[0][orig[i][j]]) {
          rep[j]++;
          matched.upd(orig[i][j], 1);
        }
        rk += (small - rm) * num_per[n - j - 1][rep[j]] +
              rm * num_per[n - j - 1][rep[j] - 1];
        if (have[1][orig[i - 1][j]]) {
          rep[j]++;
          if (orig[i - 1][j] < orig[i][j]) rk -= num_per[n - j - 1][rep[j] - 1];
          matched.upd(orig[i - 1][j], 1);
        }
        have[0][orig[i - 1][j]] = 1;
        have[1][orig[i][j]] = 1;
        rk %= mod;
      }
    } else {
      for (int j = n - 1; j >= 0; j--) {
        long long small = all.que(orig[i][j]);
        rk += fac[n - j - 1] * small;
        rk %= mod;
        all.upd(orig[i][j], 1);
      }
    }
    if (rk < 0) rk += mod;
    ans += rk * pow(num_per[n][n], n - i - 1, mod);
    ans %= mod;
  }
  cout << ans << endl;
}

### Prompt

Please create a solution in Cpp 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 double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
struct tree_array {
  int num[2050], n, bigwei;
  void init(int nn = 2000) {
    n = nn;
    while (lowb(nn) != nn) nn -= lowb(nn);
    bigwei = nn;
    n = bigwei * 2;
    for (int i = 0; i < n; i++) num[i] = 0;
  }
  void upd(int no, int add) {
    while (no <= n) {
      num[no] += add;
      no += lowb(no);
    }
  }
  int que(int no) {
    int ans = 0;
    while (no) {
      ans += num[no];
      no -= lowb(no);
    }
    return ans;
  }
} all, matched;
const int maxn = 2010;
const int mod = 998244353;
int dp[maxn];
long long fac[maxn], invfac[maxn];
int orig[maxn][maxn], rep[maxn], have[2][maxn];
long long num_per[maxn][maxn];
int n;
long long c(int a, int b) {
  if (a < b) return 0;
  return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) scanf("%d", orig[i] + j);
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  invfac[n] = pow(fac[n], mod - 2, mod);
  for (int i = n - 1; i >= 0; i--) {
    invfac[i] = invfac[i + 1] * (i + 1) % mod;
  }
  num_per[1][0] = 1;
  num_per[1][1] = 0;
  for (int i = 2; i <= n; i++) {
    num_per[i][0] = fac[i];
    for (int j = 1; j <= i; j++) {
      num_per[i][j] = num_per[i][j - 1] - num_per[i - 1][j - 1];
      if (num_per[i][j] < 0) num_per[i][j] += mod;
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    all.init();
    matched.init();
    long long rk = 0;
    if (i > 0) {
      memset(have, 0, sizeof(have));
      for (int j = n - 1; j >= 0; j--) {
        rep[j] = rep[j + 1];
        long long small = all.que(orig[i][j]);
        long long rm = matched.que(orig[i][j]);
        all.upd(orig[i][j], 1);
        if (have[0][orig[i][j]]) {
          rep[j]++;
          matched.upd(orig[i][j], 1);
        }
        rk += (small - rm) * num_per[n - j - 1][rep[j]] +
              rm * num_per[n - j - 1][rep[j] - 1];
        if (have[1][orig[i - 1][j]]) {
          rep[j]++;
          if (orig[i - 1][j] < orig[i][j]) rk -= num_per[n - j - 1][rep[j] - 1];
          matched.upd(orig[i - 1][j], 1);
        }
        have[0][orig[i - 1][j]] = 1;
        have[1][orig[i][j]] = 1;
        rk %= mod;
      }
    } else {
      for (int j = n - 1; j >= 0; j--) {
        long long small = all.que(orig[i][j]);
        rk += fac[n - j - 1] * small;
        rk %= mod;
        all.upd(orig[i][j], 1);
      }
    }
    if (rk < 0) rk += mod;
    ans += rk * pow(num_per[n][n], n - i - 1, mod);
    ans %= mod;
  }
  cout << ans << endl;
}

```