Description

Jenny Cub is continuing her quest for mathematical knowledge. She can count, but is not very good at writing numbers. She knows the digits 1, 2, 3, and 4. Unfortunately, she doesn't realize 4 is different from 1, and so she thinks that 4 is just another way to write 1.

To practice her number writing, she plays a little game where she makes numbers with the four digits she knows and sums their values. For example:

132     = 1 + 3 + 2 = 6
112314  = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that 4 = 1)

Jenny Cub now wants to know how many such numbers can she create whose sum is a number n. For n = 2, she can make 5 numbers:

11, 14, 41, 44, and 2

For n > 2, she is having trouble forming the numbers, so she needs your help.

Input

The input will consist of an arbitrary number of integers n such that 1 <= n <= 100. Here is an sample input:

2
3

Output

For each integer read, output an single integer stating how many numbers Jenny Cub can make such that the sum of their digits is equal to n. Here is an sample output:

5
13

Approach

The problem can be solved with a recurrence relationship:

F(1) = 2
F(2) = 5
F(3) = 13
F(n) = 2 * F(n - 1) + F(n - 2) + F(n - 3)

Input/Output

• Final input: problem019.input
• Final output: problem019.output

Source Code

• Peter Bui's source code: pbui.c
• Raymond LeGrand's source code: rlegrand.cc