Coloured Wood (1/0.5 Points)

Problem Statement

Indra has $n$ piles of wood, each pile of wood has a different number of planks inside it. Each pile of wood has a different colour, the $i^{th}$ pile of wood has colour $i$ for $1 \leq i \leq n$. Each pile of wood has a different number of planks, the $i^{th}$ pile of wood has $i$ planks for $1 \leq i \leq n$.

Indra wants to make a stack of wood using these piles of planks. They do so in the following process. Indra starts with an empty stack. They then pick some number of planks (potentially none) from the first pile and add it to the top of the stack. They then pick some number of planks from the second pile and add that to the top of the stack. They continue like this for all the piles (in order).

For example, if Indra has three piles of wood, they can make potentially make a stack with the following coloured planks:

• $[1, 2]$
• $[1, 2, 3, 3]$

But they could not make these:

• $[2, 1]$ (as the planks are out of order)
• $[1,2,2,2,3]$ (as there are only $2$ planks of colour $2$)
• $[4]$ (as there is no plank of colour $4$).

Determine the number of unique stacks Indra can make. Two stacks are unique there are a different number of planks OR there is a plank in one stack which has a different colour to a plank at the same place (height) in the other stack. Output the answer modulo $998244353$.

Input Format

Your first (and only) line will contain $n$.

Output Format

Output an integer representing the number of unique stacks Indra can make modulo $998244353$.

Constraints

Subtask 1 - 50%:

• $1 \leq n \leq 12$

Subtask 2 - 50%:

• $1 \leq n \leq 10^5$

Sample Cases

1

2

Explanation 1

There are two different piles Indra can make:

1. The empty pile.
2. A pile with one plank of colour 1.

3

24

Explanation 2

There are 24 different piles Indra can make, here are a few of them:

1. $[]$ (the empty pile)
2. $[1, 2, 2, 3, 3, 3]$
3. $[1, 2, 3, 3, 3]$
4. $[1, 3]$