Problem: Let n be an integer. Consider all permutations on integers 1 to n in lexicographic order, and concatenate them into one big sequence P. For example, if n = 3, then P = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]. The length of this sequence is n ⋅ n!.

Let 1 ≤ i ≤ j ≤ n ⋅ n! be a pair of indices. We call the sequence (P_i, P_{i+1}, ..., P_{j-1}, P_j) a subarray of P. 

You are given n. Find the number of distinct subarrays of P. Since this number may be large, output it modulo 998244353 (a prime number). 

Input

The only line contains one integer n (1 ≤ n ≤ 10^6), as described in the problem statement.

Output

Output a single integer — the number of distinct subarrays, modulo 998244353.

Examples

Input


2


Output


8


Input


10


Output


19210869

Note

In the first example, the sequence P = [1, 2, 2, 1]. It has eight distinct subarrays: [1], [2], [1, 2], [2, 1], [2, 2], [1, 2, 2], [2, 2, 1] and [1, 2, 2, 1]. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
const int MAXN = 1000000;
int n;
int inv[MAXN + 1];
int fac[MAXN + 1];
int ifac[MAXN + 1];
int solve() {
  inv[1] = 1;
  for (int i = (2); i <= (n); ++i)
    inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
  fac[0] = 1;
  for (int i = (1); i <= (n); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  ifac[0] = 1;
  for (int i = (1); i <= (n); ++i)
    ifac[i] = (long long)ifac[i - 1] * inv[i] % MOD;
  int ret = 0;
  for (int k = (1); k <= (n); ++k) {
    int mlt = (long long)fac[n] * ifac[n - k] % MOD;
    ret = (ret + mlt) % MOD;
  }
  for (int k = (1); k <= (n); ++k) {
    int cur = (fac[n] + MOD - (long long)fac[n] * ifac[n - k] % MOD) % MOD;
    ret = (ret + cur) % MOD;
  }
  for (int k = (3); k <= (n); ++k) {
    int mlt = (long long)fac[n] * ifac[k] % MOD;
    int ways = (long long)(n + k - 1) * (n + k) % MOD * INV2 % MOD;
    ret = (ret + (long long)mlt * ways) % MOD;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = (long long)(k - 3) * fac[n] % MOD * ifac[k] % MOD;
    int ways = (long long)(n + k - 2) * (n + k - 1) % MOD * INV2 % MOD;
    ret = (ret + (long long)mlt * ways) % MOD;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = (long long)(k - 4) * fac[n] % MOD * ifac[k] % MOD;
    int ways = k - 1;
    ret = (ret + (long long)mlt * ways) % MOD;
  }
  for (int k = (3); k <= (n); ++k) {
    int mlt = (long long)fac[n] * ifac[k] % MOD;
    int ways = (long long)(n + k - 2) * (n + k - 1) % MOD * INV2 % MOD;
    if (k == 3)
      ways =
          (ways + MOD - (long long)(k - 2) * (k - 1) % MOD * INV2 % MOD) % MOD;
    ret = (ret + (long long)mlt * ways) % MOD;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = (long long)fac[n] * ifac[k] % MOD;
    int ways = k - 1;
    ret = (ret + (long long)mlt * ways) % MOD;
  }
  for (int ndesc = (2); ndesc <= (n); ++ndesc) {
    if (ndesc < n) {
      int mlt = (long long)fac[n] * ifac[ndesc + 1] % MOD;
      int ylim = ndesc == 2 ? n + 1 : n - (ndesc - 2);
      int ways = ((long long)(n + 1 + n - (ylim - 1) + 1) * ylim % MOD * INV2 +
                  MOD - 1) %
                 MOD;
      ret = (ret + (long long)mlt * ways) % MOD;
    }
    if (ndesc < n) {
      int mlt = (long long)(ndesc - 1) * fac[n] % MOD * ifac[ndesc + 1] % MOD;
      int ylim = n - (ndesc - 1);
      int ways = ((long long)(n + 1 + n - (ylim - 1) + 1) * ylim % MOD * INV2 +
                  MOD - 1) %
                 MOD;
      ret = (ret + (long long)mlt * ways) % MOD;
    }
    if (ndesc == n) {
      int mlt = 1;
      int ylim = 2;
      int ways = ((long long)(n + 1 + n - (ylim - 1) + 1) * ylim % MOD * INV2 +
                  MOD - 1) %
                 MOD;
      ret = (ret + (long long)mlt * ways) % MOD;
    }
  }
  {
    int len = (long long)n * fac[n] % MOD;
    int cnt = (len + MOD - 2 * n) % MOD;
    int cur = (long long)cnt * (cnt + 1) % MOD * INV2 % MOD;
    ret = (ret + cur) % MOD;
  }
  return ret;
}
void run() {
  scanf("%d", &n);
  printf("%d\n", solve());
}
bool getprev(const vector<int> &p, vector<int> &res) {
  int n = ((int)(p).size());
  for (int i = n - 2; i >= 0; --i)
    if (p[i] > p[i + 1]) {
      int j = i + 1;
      while (j + 1 < n && p[i] > p[j + 1]) ++j;
      res = p;
      swap(res[i], res[j]);
      reverse(res.begin() + i + 1, res.end());
      return true;
    }
  return false;
}
bool getnext(const vector<int> &p, vector<int> &res) {
  int n = ((int)(p).size());
  for (int i = n - 2; i >= 0; --i)
    if (p[i] < p[i + 1]) {
      int j = i + 1;
      while (j + 1 < n && p[i] < p[j + 1]) ++j;
      res = p;
      swap(res[i], res[j]);
      reverse(res.begin() + i + 1, res.end());
      return true;
    }
  return false;
}
void gen(const vector<int> &pcur, int lpref, int hpref, int nmid, int lsuff,
         int hsuff, vector<string> &have, char id) {
  int n = ((int)(pcur).size());
  vector<int> pbef;
  assert(getprev(pcur, pbef));
  vector<int> pbf2;
  bool havebf2 = getprev(pbef, pbf2);
  vector<int> pnxt;
  bool havenxt = getnext(pcur, pnxt);
  for (int pref = lpref; pref + nmid <= 2 * n && pref <= hpref; ++pref)
    for (int suff = lsuff; pref + nmid + suff <= 2 * n && suff <= hsuff;
         ++suff) {
      string t(pref + nmid + suff, '?');
      for (int i = (0); i < (((int)(t).size())); ++i) {
        int idx = i - pref;
        if (idx >= 0 && idx < n)
          t[i] = '0' + pcur[idx];
        else if (idx + n >= 0 && idx + n < n)
          t[i] = '0' + pbef[idx + n];
        else if (idx + 2 * n >= 0 && idx + 2 * n < n)
          t[i] = '0' + (havebf2 ? pbf2[idx + 2 * n] : 0);
        else if (idx - n >= 0 && idx - n < n)
          t[i] = '0' + (havenxt ? pnxt[idx - n] : 0);
        else
          assert(false);
      }
      bool ok = true;
      for (int i = (0); i < (((int)(t).size())); ++i)
        if (t[i] == '0') ok = false;
      if (!ok) continue;
      have.push_back(t);
    }
}
void gen(const vector<int> &pcur, int lpref, int nmid, int lsuff,
         vector<string> &have, char id) {
  gen(pcur, lpref, 2 * ((int)(pcur).size()), nmid, lsuff,
      2 * ((int)(pcur).size()), have, id);
}
void research() {
  int n = 3;
  string s;
  vector<int> p(n);
  for (int i = (0); i < (n); ++i) p[i] = i + 1;
  do {
    for (int i = (0); i < (((int)(p).size())); ++i) s += string(1, '0' + p[i]);
  } while (next_permutation(p.begin(), p.end()));
  printf("SZ(s)=%d\n", ((int)(s).size()));
  if (((int)(s).size()) <= 1000) printf("s:%s\n", s.c_str());
  vector<string> want;
  for (int i = (0); i < (((int)(s).size())); ++i) {
    vector<bool> seen(n, false);
    bool ok = false;
    for (int j = (i); j < (((int)(s).size())); ++j) {
      int len = j - i + 1;
      if (len > 2 * n) break;
      int x = s[j] - '1';
      if (seen[x])
        ok = true;
      else
        seen[x] = true;
      if (ok && len <= 2 * n) want.push_back(s.substr(i, j - i + 1));
    }
  }
  sort(want.begin(), want.end());
  want.erase(unique(want.begin(), want.end()), want.end());
  printf("SZ(want)=%d\n", ((int)(want).size()));
  vector<int> fac(n + 1);
  fac[0] = 1;
  for (int i = (1); i <= (n); ++i) fac[i] = fac[i - 1] * i;
  int guess = 0;
  for (int k = (1); k <= (n); ++k) {
    int cur = fac[n] - fac[n] / fac[n - k];
    guess += cur;
  }
  for (int k = (3); k <= (n); ++k) {
    int mlt = fac[n] / fac[k];
    int ways = (n + k - 1) * (n + k) / 2;
    guess += mlt * ways;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = (k - 3) * fac[n] / fac[k];
    int ways = (n + k - 2) * (n + k - 1) / 2;
    guess += mlt * ways;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = (k - 4) * fac[n] / fac[k];
    int ways = k - 1;
    guess += mlt * ways;
  }
  for (int k = (3); k <= (n); ++k) {
    int mlt = fac[n] / fac[k];
    int ways = (n + k - 2) * (n + k - 1) / 2;
    if (k == 3) ways -= (k - 2) * (k - 1) / 2;
    guess += mlt * ways;
  }
  for (int k = (4); k <= (n); ++k) {
    int mlt = fac[n] / fac[k];
    int ways = k - 1;
    guess += mlt * ways;
  }
  for (int ndesc = (2); ndesc <= (n); ++ndesc) {
    if (ndesc < n) {
      int mlt = fac[n] / fac[ndesc + 1];
      int ylim = ndesc == 2 ? n + 1 : n - (ndesc - 2);
      int ways = (n + 1 + n - (ylim - 1) + 1) * ylim / 2 - 1;
      guess += mlt * ways;
    }
    if (ndesc < n) {
      int mlt = (ndesc - 1) * fac[n] / fac[ndesc + 1];
      int ylim = n - (ndesc - 1);
      int ways = (n + 1 + n - (ylim - 1) + 1) * ylim / 2 - 1;
      guess += mlt * ways;
    }
    if (ndesc == n) {
      int mlt = 1;
      int ylim = 2;
      int ways = (n + 1 + n - (ylim - 1) + 1) * ylim / 2 - 1;
      guess += mlt * ways;
    }
  }
  vector<string> have;
  for (int midmask = (0); midmask < (1 << n); ++midmask) {
    vector<int> mid, oth;
    for (int i = (0); i < (n); ++i)
      if (midmask & (1 << i))
        mid.push_back(i + 1);
      else
        oth.push_back(i + 1);
    int k = ((int)(oth).size());
    if (k == 2) do {
        vector<int> pcur(n);
        for (int i = (0); i < (((int)(mid).size())); ++i) pcur[i] = mid[i];
        pcur[((int)(mid).size())] = oth[1];
        pcur[((int)(mid).size()) + 1] = oth[0];
        int ridx = n - 2;
        while (ridx >= 0 && pcur[ridx] > pcur[ridx + 1]) --ridx;
        int hpref = n, hsuff = ridx < 0                      ? 2
                               : pcur[ridx] < pcur[ridx + 2] ? 2 + ridx
                               : ridx < n - 3                ? 2 + ridx + 1
                                                             : n + 1;
        gen(pcur, 1, hpref, ((int)(mid).size()), 1, hsuff, have, 'A');
      } while (next_permutation(mid.begin(), mid.end()));
    if (k >= 3) do {
        vector<int> pcur(n);
        for (int i = (0); i < (((int)(mid).size())); ++i) pcur[i] = mid[i];
        pcur[((int)(mid).size())] = oth[1];
        pcur[((int)(mid).size()) + 1] = oth[0];
        for (int i = (2); i < (((int)(oth).size())); ++i)
          pcur[((int)(mid).size()) + i] = oth[i];
        gen(pcur, 1, ((int)(mid).size()), 1, have, 'B');
      } while (next_permutation(mid.begin(), mid.end()));
    if (k >= 3) do {
        vector<int> pcur(n);
        for (int i = (0); i < (((int)(mid).size())); ++i) pcur[i] = mid[i];
        pcur[((int)(mid).size())] = oth[2];
        pcur[((int)(mid).size()) + 1] = oth[0];
        pcur[((int)(mid).size()) + 2] = oth[1];
        for (int i = (3); i < (((int)(oth).size())); ++i)
          pcur[((int)(mid).size()) + i] = oth[i];
        int hpref = k == 3 ? n : 2 * n;
        gen(pcur, 1, hpref, ((int)(mid).size()), 2, 2 * n, have, 'C');
        gen(pcur, n + 1, hpref, ((int)(mid).size()), 1, 1, have, 'D');
      } while (next_permutation(mid.begin(), mid.end()));
    if (k >= 4)
      for (int pos = (3); pos < (((int)(oth).size())); ++pos) do {
          vector<int> pcur(n);
          for (int i = (0); i < (((int)(mid).size())); ++i) pcur[i] = mid[i];
          pcur[((int)(mid).size())] = oth[pos];
          for (int i = (1); i < (((int)(oth).size())); ++i)
            pcur[((int)(mid).size()) + i] = oth[i <= pos ? i - 1 : i];
          gen(pcur, 1, ((int)(mid).size()), 2, have, 'E');
          int hsuff = ((int)(mid).size()) + pos < n - 1 ? 2 * n : n;
          gen(pcur, n + 1, hsuff, ((int)(mid).size()), 1, 1, have, 'F');
        } while (next_permutation(mid.begin(), mid.end()));
    if (k >= 1) do {
        bool ok = false;
        for (int i = (1); i < (((int)(mid).size())); ++i)
          if (mid[i - 1] < mid[i]) ok = true;
        if (!ok) continue;
        do {
          string t(
              ((int)(oth).size()) + ((int)(mid).size()) + ((int)(oth).size()),
              '?');
          for (int i = (0); i < (((int)(oth).size())); ++i)
            t[i] = t[n + i] = '0' + oth[i];
          for (int i = (0); i < (((int)(mid).size())); ++i)
            t[((int)(oth).size()) + i] = '0' + mid[i];
          have.push_back(t);
        } while (next_permutation(oth.begin(), oth.end()));
      } while (next_permutation(mid.begin(), mid.end()));
  }
  printf("SZ(have)=%d guess=%d\n", ((int)(have).size()), guess);
  sort(have.begin(), have.end());
  for (int i = (1); i < (((int)(have).size())); ++i)
    if (have[i] == have[i - 1]) printf("double: %s\n", have[i].c_str());
  have.erase(unique(have.begin(), have.end()), have.end());
}
int main() {
  run();
  return 0;
}