Challenge 22: Counting

Caleb is now in elementary school and is developing his mathematical knowledge. He is pretty good at counting, but still struggles with writing numbers ¹. 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.

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.

Submission

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

$ cd path/to/cse-30872-fa17-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 challenge22               # Create and checkout challenge22 branch

$ $EDITOR challenge22/program.cpp           # Edit your code

$ git add challenge22/program.cpp           # Stage your changes
$ git commit -m "challenge22: done"         # Commit your changes

$ git push -u origin challenge22            # Send changes to GitLab

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

$ .scripts/submit.py
Submitting challenge22 assignment ...
Submitting challenge22 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge22/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge22
{"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.