Decomposing into Prime Sums

In this problem, you are given a positive integer \(n\). Your task is to count the total number of ways to decompose \(n\) as a sum of prime numbers. In each decomposition, the primes are considered in non-decreasing order. For example, the number \(4\) can only be decomposed as \(2+2\), and thus has 1 valid representation.

The problem is inspired by various musings:

• \(1+1=?\) Obviously, the answer is \(2\).
• \(a+b=?\) Refer to problem P1001 for details.
• There is a playful reference to Goldbach's conjecture trending in popularity.

The above are just personal remarks.

Now, given \(n\), output the number of ways to write \(n\) as a sum of prime numbers.

inputFormat

The input consists of a single positive integer \(n\) (\(1 \le n \le 10^4\)).

outputFormat

Output a single integer representing the total number of ways to decompose \(n\) into the sum of prime numbers. If there is no way, output 0.

sample

2

1