Counting Readable Words

Ellenora has observed an interesting fact about the human brain: when reading, it mainly processes the first and last letters of each word. Inspired by this, she considers that by "mixing up" some letters (for example, letters such as l and i, a and o, x and m are very similar) one may obtain better results. In her idea, every adjacent pair of letters in a word is assigned a value between (1) and (5) (with the rule that identical letters always contribute a cost of (1)). Consequently, the value of a word is defined as the sum of the values of all adjacent letter pairs. Note that a word with a single letter has a value of (0) and, importantly, every time a letter is added the word’s value increases by at least (1) (i.e. the minimal possible increase is (1)).

Ellenora wants to construct a language that remains easy to read even if many letters are mixed up. To do so she will include in her lexicon every non‐empty word whose value is at most (N). Your task is to determine how many such words there are.

Observations:

1. Every word with (L) letters ((L\ge 1)) has exactly (L-1) adjacent pairs. Hence, its minimum possible value is (L-1) (this happens when every adjacent pair is identical, each contributing (1)).
2. Instead of considering the letters and their pair–wise similarity, one may observe that every non–empty word corresponds uniquely to a sequence of costs (one for each adjacent pair) where each cost is an integer from the set ({1,2,3,4,5}). In the case of a single letter (i.e. an empty sequence) the word’s value is (0).

Thus, the problem reduces to the following: Count the number of (possibly empty) sequences (a_1,a_2,\dots,a_k) (with (k\ge 0)) such that (a_i\in{1,2,3,4,5}) for every (i) and the total sum (a_1+\dots+a_k) does not exceed (N). (Remember that the empty sequence corresponds to a one–letter word and is counted as well.)

Input Format: A single integer (N).

Output Format: Print the number of valid words whose value does not exceed (N).

inputFormat

The input consists of a single integer (N) representing the maximum allowed value for a word.

outputFormat

Output a single integer which is the number of non‐empty words (or equivalently, sequences of costs corresponding to the letter transitions) whose total value does not exceed (N).

sample

1

2