sume3

Да разгледаме цяло положително число N. Има различни начини за представянето на N като сума от степени на числото 3.
Например за числото
10, има 5 разбивания:
1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+3
1+1+1+1+3+3
1+3+3+3
1+9

Задача

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

Вход

Входният файл  sume3.in  съдържа на първия ред цялото положително число N.

Изход

Изходният файл  sume3.out  трябва да съдържа единствен ред, на който е записан броя на представянията на числото N като сума от степени на числото 3. Ако намереното число е по-голямо или равно на 1000000000, да се изведат само последните 9 цифри на резултата.

Ограничения

Пример

sume3.in

sume3.out

10

5

Ограничение за време: 0.2 секунди на тест

prof. Dana Lica
"I. L. Caragiale" National College, Ploieşti
Contact:danal182001@yahoo.com

Превод на български: Стоян Капралов