#include #include #include #include #include #include #include using namespace std; using lint = long long; template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } #include using mint = atcoder::modint998244353; template struct acl_fac { std::vector facs, facinvs; acl_fac(int N) { assert(-1 <= N and N < modint::mod()); facs.resize(N + 1, 1); for (int i = 1; i <= N; i++) facs[i] = facs[i - 1] * i; facinvs.assign(N + 1, facs.back().inv()); for (int i = N; i > 0; i--) facinvs[i - 1] = facinvs[i] * i; } modint ncr(int n, int r) const { if (n < 0 or r < 0 or n < r) return 0; return facs[n] * facinvs[r] * facinvs[n - r]; } modint npr(int n, int r) const { if (n < 0 or r < 0 or n < r) return 0; return facs[n] * facinvs[n - r]; } modint operator[](int i) const { return facs[i]; } modint finv(int i) const { return facinvs[i]; } }; acl_fac fac(201010); int lislen(const vector &a) { constexpr int INF = 1 << 30; vector dp(a.size() + 2, INF); dp[0] = -INF; int maxlen = 0; for (auto x : a) { int i = argub(dp, x); dp[i] = x; chmax(maxlen, i); } return maxlen; } lint bruteforce(int n, int m) { vector A(n + m); iota(A.begin(), A.end(), 0); lint ret = 0; do { int u = lislen(A); if (u != n) continue; vector B; for (auto x : A) B.push_back(-x); int v = lislen(B); if (v == m) ++ret; } while (next_permutation(A.begin(), A.end())); return sqrtl(ret); } // -> https://oeis.org/A059797 // T[n_, k_] := (k + 1)(n + k +4) FactorialPower[k + n + 2, n]/(n! + (n + 1)!) mint A059797(int n, int k) { mint ret = mint(k + 1) * mint(n + k + 4) * (fac[n] + fac[n + 1]).inv(); ret *= fac.npr(k + n + 2, n); return ret; } // # of permutation of a = (1, 2, ..., n + m) s.t. len(lis(a)) == n and len(lds(a)) == m mint solve(int n, int m) { if (n <= 1 or m <= 1) return 0; return A059797(n - 2, m - 2).pow(2); } int main() { int N; cin >> N; mint ret = 0; for (int lislen = 0; lislen <= N; ++lislen) { int ldslen = N - lislen; ret += solve(lislen, ldslen); } cout << ret.val() << endl; }