Nested Product Exponentiation

Given an integer n, compute the following expression modulo 998244353:

$$\prod_{i=1}^{n}\prod_{j=1}^{i}\prod_{k=1}^{j} k^k$$

This can be reformulated as computing:

$$\prod_{j=1}^{n} \left(\prod_{k=1}^{j} k^k\right)^{n-j+1}$$

and finally output the answer modulo 998244353.

inputFormat

The input consists of a single integer n (1 ≤ n).

outputFormat

Output a single integer, which is the value of the nested product modulo 998244353.

sample

1

1