Description

• $1+1=?$ Obviously $2$.
• $a+b=?$ See P1001, don't thank me.
• Goldbach's conjecture seems to be everywhere.

The above is purely a personal rant.

Given a positive integer $n$, find the total number of ways to express it as a sum of prime numbers. The order of addends does not matter.

Input Format

One line containing a positive integer $n$.

Output Format

One line containing an integer representing the total number of ways.

7

3

20

26

Hint

Sample Explanation

There are the following three ways:

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

Constraints

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

Translated by ChatGPT 5