AT_fps_24_o 根付き木

Consider rooted trees with $ N $ vertices, where the vertices are labeled $ 1 $ through $ N $ , and vertex $ 1 $ is the root. Count how many such rooted trees satisfy the following condition, and output the result modulo $ 998244353 $ . - For every integer $ i $ such that $ 1 \leq i \leq N $ , the number of children of vertex $ i $ is either $ 0 $ or a prime number.

The input is given from standard input in the following format: > $ N $

Print the answer.

### Sample Explanation 1 For example, consider the rooted tree where both vertex $ 2 $ and vertex $ 3 $ have parent $ 1 $ . This satisfies the condition because vertex $ 1 $ has $ 2 $ children (a prime number), and vertices $ 2 $ and $ 3 $ both have $ 0 $ children. This is the only rooted tree that satisfies the condition. ### Constraints - $ 3 \leq N \leq 2.5 \times 10^5 $ - $ N $ is an integer