题意：
问你$1\sim n$的所有排列的最长上升子序列的期望长度。
题解：
开始想了个假的东西，发现是$O(\frac{2^n}n)$的，貌似可以过，然后发现假掉了。。然后发现正解是不能在时限里跑出来的，所以都是打表的。。
如果现在有一个排列，设$f_i$为以第$i$位结尾的LIS的长度，$mx_i$为$f$的前缀最大值。显然$mx_i$和$mx_{i + 1}$的差值是不会超过$1$的，所以我们就可以状压$mx$的差分。假如现在我们知道一个$1\sim i$的排列，然后插入$i + 1$，假如插入在位置$k$和$k + 1$之间，那对$mx$的影响就是先在$k + 1$位置插入$mx_k + 1$，然后把所有$= mx_k$的$mx$加$1$。反映到差分数组上就是在$k + 1$位置插入一个$1$，然后把$k$后面第一个$1$改成$0$。
然后就可以$dp$了。$f_{i, j}$表示$1~i$的排列$mx$的差分是$j$的方案数。显然一个状态的LIS就是$j$中$1$的个数。答案就把$f$和$1$的个数乘起来就好了。
极限数据上个厕所就跑出来了233
注释中是打表代码。
// #include <bits/stdc++.h>
// using namespace std;
// const int mod = 998244353;
// int n, f[2][134217728], cnt[134217728];
// long long ans = 0;
// int lb(int x) { return x & -x; }
// long long Pow(long long x, long long y)
// {
// if (y == 0) return 1;
// long long ans = Pow(x, y >> 1);
// ans = ans * ans % mod;
// if (y & 1) ans = ans * x % mod;
// return ans;
// }
// int main()
// {
// scanf("%d", &n);
// int p = 1;
// f[p][0] = 1;
// for (int i = 1; i < n; i++, p ^= 1)
// {
// memset(f[p ^ 1], 0, sizeof(f[p ^ 1]));
// for (int j = 0; j < (1 << i - 1); j++)
// {
// (f[p ^ 1][j << 1] += f[p][j]) %= mod;
// for (int k = 0; k < i; k++)
// {
// int hh1 = j & (1 << k) - 1, hh2 = j - hh1;
// hh2 -= lb(hh2);
// (f[p ^ 1][hh1 + (hh2 << 1) + (1 << k)] += f[p][j]) %= mod;
// }
// }
// }
// cnt[0] = 1;
// for (int i = 0; i < (1 << n - 2); i++)
// {
// cnt[i << 1] = cnt[i];
// cnt[i << 1 | 1] = cnt[i] + 1;
// }
// for (int i = 0; i < (1 << n - 1); i++)
// (ans += 1LL * f[p][i] * cnt[i] % mod) %= mod;/*
// for (int i = 0; i < (1 << n - 1); i++)
// printf("%d\n", f[n][i]);*/
// long long fac = 1;
// for (int i = 1; i <= n; i++) fac = fac * i % mod;
// printf("%lld\n", ans * Pow(fac, mod - 2) % mod);
// }
#include <bits/stdc++.h>
using namespace std;
int a[] = {0, 1, 499122178, 2, 915057326, 540715694, 946945688, 422867403, 451091574, 317868537, 200489273, 976705134, 705376344, 662845575, 331522185, 228644314, 262819964, 686801362, 495111839, 947040129, 414835038, 696340671, 749077581, 301075008, 314644758, 102117126, 819818153, 273498600, 267588741}, n;
int main()
{
scanf("%d", &n);
printf("%d\n", a[n]);
}