Задача “Магічні суми”

(Обмеження часу: 6 с, Обмеження пам’яті: 64 мбайт)

Ім’я вхідного файлу:  simsum.dat

Ім’я вихідного файлу: simsum.ans

Програма: simsum.*

Гаррі Поттер  вивчаючи прості числа, мав взнати, що будь-яке ціле число більше 1 можна єдиним способом представити у вигляді добутку простих множників. Але при вивченні арифметики разом із Роном Уізлі, вони замість добутку вирішили представляти цілі числа у вигляді суми простих доданків (в не спадаючому порядку), і виявили, декілька таких сум. Так для числа 13 є 9 таких сум: 13=13, 13=2+2+2+2+2+3, 13=2+2+3+3+3, 13=2+3+3+5, 13=2+2+2+2+5, 13=3+5+5, 13=2+2+2+7, 13=3+3+7, 13=2+11.

Допоможіть друзям визначити кількість сум для будь-якого числа.

Формат вхідних даних :

Вхідний файл містить одне ціле число N (1<N≤5000).

Формат вихідних даних :

У вихідний файл вивести кількість сум.

Приклад:

Вхідні дані: 13

Вихідні дані: 9