题目描述

我们都知道,大于 $1$ 的整数如果只有 $1$ 和它本身两个因数,就叫做素数。

现在给定一个正整数 $n$,请你数一数:把 $n$ 表示成若干个素数相加的形式,一共有多少种不同的表示方法。表示方法只关心每个素数出现了多少次——如果两种写法仅仅是加数的排列顺序不同,就视为同一种方案。

注意:当 $n$ 本身是素数时,单独一个 $n$ 也算一种合法的表示。

输入格式

一行一个正整数 $n$。

输出格式

输出一行一个整数,表示方案总数。

样例

7

3

20

26

提示

样例说明

以 $n=7$ 为例,共有以下三种表示方法:

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

数据范围及约定

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