Satori, the bunny store owner, decided to offer a discount to whoever answered her problem:

What's the number of different Max-heaps build on \(N\) different key values?

Note that two heaps are considered different if and only if the two binary trees have different pre-order traversals.

A single integer \(N(1\leq N\leq 1000)\)

Output a single integer indicating the number of different Max-heaps module \(998244353\)

Note that 998244353 is a prime number.

This problem is not difficult.