Coding is the closest thing we have to superpower !

2492 : 背包-练习-素数之和
描述

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

输入

一行一个正整数 n。

对于 30% 的数据,1≤n≤10。

对于 100% 的数据,1≤n≤1000。

输出

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

样例

输入

7

输出

3

输入

20

输出

26
提示

【样例说明】

存在如下三种方案:

  • 7=7。
  • 7=2+5。
  • 7=2+2+3。
标签
语言:
主题: