Challenge 10: Counting

Abigail and Madeline are now in year two of elementary school and have been developing their mathematical knowledge. They are pretty good at counting, but still struggle with writing numbers ¹. They know the digits 1, 2, 3, and 4 pretty well. Unfortunately, they sometimes don't realize 4 is different from 1, so they think that 4 is just another way to write 1.²

To practice their number writing, Abigail and Madeline play a little game where they makes numbers with the four digits they know and sums the values. For example:

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

Abigail and Madeline now want to know how many such numbers can they create whose sum is a number n. For n = 2, they can make 5 numbers:

11, 14, 41, 44, 2

For n > 2, they are having trouble forming the numbers, so Abigail and Madeline need 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 Abigail and Madeline can make such that the sum of the digits is equal to n.

Example Output

5
13

Submission

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

$ cd path/to/cse-34872-su20-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge10               # Create and checkout challenge10 branch

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

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

$ git push -u origin challenge10            # Send changes to GitHub

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

$ .scripts/submit.py
Submitting challenge10 assignment ...
Submitting challenge10 code ...
  Result Success
   Score 6.00
    Time 0.02

$ curl -F source=@challenge10/program.cpp https://dredd.h4x0r.space/code/cse-34872-su20/challenge10
{"result": "Success", "score": 6, "time": 0.016405344009399414}