Decomposition into simple addends#389
Sign in

Decomposition into simple addends

1 second
128 megabytes
Medium

An integer greater than can be uniquely written as the product of prime factors if the factors are listed in non-decreasing order. However, when presenting an integer as a sum of prime numbers (also listed in non-decreasing order), there may be several different decompositions. For example, the number can be decomposed into primes in different ways:

11 = 11
11 = 2 + 2 + 7
11 = 3 + 3 + 5
11 = 2 + 2 + 2 + 5
11 = 2 + 3 + 3 + 3
11 = 2 + 2 + 2 + 2 + 3

Write a program to find the number of ways the given number can be decomposed into a sum of prime addends.

Input

A single natural number (1 < n \leq 5000).

Output

Print the number of decompositions of the given number into prime addends.

Examples

Example 1

Loading
Loading