Sum of Permutation Counts

Consider all binary strings \(s = s_1 s_2 \cdots s_n\) of length \(n\), where each character is either ''. For each such string \(s\), define \(f(s)\) as the number of permutations \(p_1, p_2, \dots, p_{n+1}\) of \(\{1, 2, \dots, n+1\}\) that satisfy the condition

[ p_i < p_{i+1} \iff s_i = \text{<} \quad \text{for } 1 \le i \le n, ]

Your task is to compute the sum of \(f(s)\) over all \(2^n\) possible binary strings \(s\), and output the answer modulo \(998244353\).

Observation: Every permutation of \(\{1,2,\dots,n+1\}\) produces exactly one binary string (its ascent/descent pattern). Hence, the sum of \(f(s)\) over all \(s\) is exactly \((n+1)!\). That is, the answer is \((n+1)! \bmod 998244353\).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le \text{some limit}\)).

outputFormat

Output one integer: \((n+1)! \bmod 998244353\).

sample

1

2