Caleb is now in year three of elementary school and is developing his mathematical knowledge. He is pretty good at counting, but still struggles with writing numbers 1. He knows the digits `1`, `2`, `3`, and `4` pretty well. Unfortunately, he sometimes doesn't realize `4` is different from `1`, so he thinks that `4` is just another way to write `1`.2

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

``````132     = 1 + 3 + 2 = 6
112314  = 1 + 1 + 2 + 3 + 1 + 1 = 9     # Remember that 4 = 1``````

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

``11, 14, 41, 44, 2``

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

## Input

The input will consist of an arbitrary number of integers `n` such that ```1 <= n <= 1000```.

### Example Input

``````2
3``````

## Output

For each integer read, output an single integer stating how many numbers Caleb can make such that the sum of their digits is equal to `n`.

### Example Output

``````5
13``````

## Hints

Some things to consider:

1. You may wish to find a recurrence relation rather than brute-forcing.
2. You may wish to use memoization.
3. The answers will be quite large and will require big integers.

#### Programming Challanges

This is based on 10198 - Counting problem on the UVa Online Judge.

## Submission

``````\$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitLab

\$ git checkout -b challenge23               # Create and checkout challenge23 branch

\$ \$EDITOR challenge23/program.cpp           # Edit your code

\$ git commit -m "challenge23: done"         # Commit your changes

\$ git push -u origin challenge23            # Send changes to GitLab``````

To check your code, you can use the `.scripts/submit.py` script or curl:

``````\$ .scripts/submit.py
Submitting challenge23 assignment ...
Submitting challenge23 code ...
Result Success
Score 6.00
Time 0.02

\$ curl -F source=@challenge23/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge23
{"score": 6, "result": "Success"}``````

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 11 TA List to determine your corresponding TA for the merge request.

1. Like father, like son.

2. Not true, but I needed a story.