問題文

正の整数 $N$ が与えられます。ここで、$N$ は $3$ の倍数であることが保証されます。

$\{ 1,2,\dots ,N \}$ の順列 $(P_{1},P_{2},\dots ,P_{N})$ であって、次の条件が満たされるものの個数を $998244353$ で割った余りを答えてください。

• $1\leq i\leq N$ を満たす全ての整数 $i$ について、$P_{i} \leq \frac{N}{3}$ と $P_{i}< \min(P_{i-1},P_{i+1})$ のうち片方のみが満たされるものが存在しない。ただし、 $P_{0}=P_{N}$ 、 $P_{N+1}=P_{1}$ とする。

制約

• $N$ は整数
• $N$ は $3$ の倍数
• $3\leq N\leq 9999999$

入力

N

出力

答えを出力してください。

サンプル

3

6

この場合、$P_{i}=1$ ならば隣り合う要素は $2,3$ であるため条件を満たし、$P_{i}\neq 1$ ならば隣り合う要素に $1$ が含まれるため条件を満たします。よって、求めるべき答えは $3!=6$ です。

12

47029248

この場合、条件は $P_{i}\leq 4$ ならば $P_{i}< \min(P_{i-1},P_{i+1})$ 、$4<P_{i}$ ならば $\min(P_{i-1},P_{i+1})<P_{i}$ となります。

9982443

198511167

$998244353$ で割った余りを答えることに注意してください。