J17 实践-3 质数和分解

题目描述

任何大于 $1$ 的自然数 $n$ 都可以写成若干个大于等于 $2$ 且小于等于 $n$ 的质数之和表达式（包括只有一个数构成的和表达式的情况），并且可能有不止一种质数和的形式。例如，$9$ 的质数和表达式就有四种本质不同的形式：$9=2+5+2=2+3+2+2=3+3+3=2+7$ 。 这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。 试编程求解自然数 $n$ 可以写成多少种本质不同的质数和表达式。

输入格式

一个自然数 $n$。

输出格式

输出 $n$ 的本质不同的质数和表达式的数目，答案对$998244353$取模。

样例输入

10

样例输出

5

样例分析

如上所述。

数据范围

对于 $50\%$ 的数据：$2 \leq n \leq 100$ 。

对于 $100\%$ 的数据：$2 \leq n \leq 10000$ 。