Let's take a positive integer N. There is more than one way to decompose it as a sum of powers of 3.
For example, for number 10, there
are 5 decompositions:
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
Task
Write a program that determines the number of decompositions of a positive integer N as a sum of powers of 3.
Input Data
Input file sume3.in contains on the first line a positive integer N
Output Data
Output file sume3.out will contain a single line with the number of decompositions of N as the sum of powers of 3. If the number obtained is larger than or equal to 1000000000, display only the last 9 digits of the number.
Constraints and Statements
| sume3.in | sume3.out |
|
10 |
5 |
Time limit: 0.2 seconds/test
prof. Dana Lica
"I. L. Caragiale" National College, Ploieşti
Contact:danal182001@yahoo.com