P15059

A+B Problem（再升级）

题目描述

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

输入

一行一个正整数 n。

输出

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

样例

样例 1

输入

7

输出

3
样例 2

输入

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