Problem Background

The title of the problem is designed to attract your attention.

In reality, the problem is still quite straightforward.

Problem Description

• $1+1=?$ Obviously, it's $2$.
• $a+b=?$ Refer back to P1001 if you need.
• The Goldbach Conjecture seems to be overused.

The above is purely personal commentary

Given a positive integer $n$, find the total number of ways to decompose it into the sum of several prime numbers.

Input Format

A single line containing a positive integer $n$.

Output Format

A single line containing an integer representing the total number of ways.

Sample Input and Output

Sample Input #1

7

Sample Output #1

3

Sample Input #2

20

Sample Output #2

26

Notes

Sample Explanation

There are three possible ways:

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

Data Range and Constraints

• For $30\%$ of the data, $1 \le n \le 10$.
• For $100\%$ of the data, $1 \le n \le 10^3$.

见题面 Input 部分

见题面 Output 部分