3810 - A+B Problem（再升级）

给定一个正整数 n，求将其分解成若干个素数之和的方案总数。

输入

一行一个正整数 n。

输出

一行一个整数表示方案总数。

样例

输入

7

输出

3

输入

20

输出

26

提示

样例解释

存在如下三种方案：

  • 7=7。
  • 7=2+5。
  • 7=2+2+3。

数据范围及约定

  • 对于 30\% 的数据 1\le n\le 10。
  • 对于 100\% 的数据，1\le n\le 10^3。

来源

luogu

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题