Decomposition into simple addends

An integer greater than 1 can be uniquely expressed as a product of prime factors when the factors are arranged in non-decreasing order. However, when expressing integers as a sum of prime numbers, also arranged in non-decreasing order, multiple decompositions are possible. For instance, the number 11 can be decomposed into prime addends in 6 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 determine the number of ways a given number can be decomposed into a sum of prime addends.

Input

A single natural number n where 1 < n ≤ 5000.

Output

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

Examples