Count Prime Sum Representations

Given a natural number \(n\) greater than \(1\), it is known that \(n\) can be expressed as a sum of one or more prime numbers (each prime is at least \(2\) and at most \(n\)). The expression may consist of a single prime (if \(n\) is prime) and there can be more than one essentially different representation. Two expressions are considered essentially the same if one can be obtained from the other by reordering the summands.

For example, for \(n = 9\), there are four essentially different representations: \[ 9 = 2 + 7 = 3 + 3 + 3 = 2 + 2 + 5 = 2 + 2 + 2 + 3 \]

Your task is to write a program that computes the number of essentially different representations of \(n\) as a sum of primes.

Note: Use \(\LaTeX\) format for any mathematical formulas.

inputFormat

The input consists of a single natural number \(n\) (\(n > 1\)).

outputFormat

Output the number of essentially different representations of \(n\) as a sum of primes.

sample

9

4