Background

Red problems make people "red-hot" (hong wen).

Problem Description

Compute $\prod \limits_{i=1}^{n} \prod\limits_{j=1}^{i} \prod \limits_{k=1}^{j} k^k$ modulo $998244353$.

Input Format

The input contains $1$ line with $1$ integer, which is $n$.

Output Format

Output $1$ line with $1$ integer, which is the answer.

3

1728

Hint

Constraints

• For $20\%$ of the testdata, $n\leq5\times10^2$.
• For $50\%$ of the testdata, $n\leq5\times10^3$.
• For $100\%$ of the testdata, $1\leq n\leq1.8\times10^6$.

Translated by ChatGPT 5