Любое целое число, большее 1 можно единственным способом представить в виде произведения простых множителей (если перечислять множители в неубывающем порядке). Но если попытаться представлять целые числа в виде суммы простых слагаемых (также в неубывающем порядке), то таких разложений окажется несколько. Например, для числа 11 есть 6 таких разложений: 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.

Напишите программу, которая найдет количество разложений данного числа на простые слагаемые.

Входные данные

Одно натуральное число n (1 < n ≤ 5000).

Выходные данные

Выведите количество разложений числа n на простые слагаемые.