Set Partition Count

Given a set with \(n\) elements, partition it into one or more non-empty subsets. The subsets are unordered, meaning that partitions which differ only in the order of subsets are considered identical. Formally, you are asked to compute the number of ways to partition a set of \(n\) elements. Since the answer can be very large, output it modulo \(998244353\).

The mathematical formulation of the problem is to compute the Bell number \(B(n)\) modulo \(998244353\), where \(B(n)\) is defined by:

[ B(n+1) = \sum_{i=0}^{n} \binom{n}{i} B(i), \quad B(0)=1. ]

inputFormat

The input consists of a single integer \(n\) indicating the number of elements in the set.

outputFormat

Output a single integer, which is the number of ways to partition the set modulo \(998244353\).

sample

1

1