Expected Length of Longest Increasing Subsequence

Given a random permutation of length $n$, compute the expected value of the length of its longest increasing subsequence (LIS). Formally, let $$E = \frac{1}{n!}\sum_{\pi \in S_n} \mathrm{LIS}(\pi),$$ where $S_n$ is the set of all permutations of $\{1,2,\dots,n\}$. To avoid issues with precision, output the value of $E$ modulo $998244353$.

Note: In this problem, $n$ is small (for example, $1 \le n \le 8$) so that it is feasible to iterate over all permutations.

inputFormat

Input consists of a single line containing one integer $n$ ($1\le n\le 8$), representing the length of the permutation.

outputFormat

Output a single integer — the expected length of the longest increasing subsequence modulo $998244353$.

sample

1

1