Довільне ціле число більше 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).

Вихідні дані

Вивести кількість розкладів заданого числа на прості доданки.