Любое целое число большее 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).

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

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