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.

The input will consist of an arbitrary number of integers `n`

such that ```
1 <=
n <= 1000
```

.

```
2
3
```

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`

.

```
5
13
```

Some things to consider:

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

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

To submit your work, follow the same procedure you used for Reading 00:

```
$ 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 add challenge23/program.cpp # Stage your changes
$ 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.