Problem Description

$\rm Finn$ really likes $4$ and $5$. He believes that every number can be obtained by adding $4$ and $5$.

Examples:

$14 = 5 + 5 + 4$

$20 = 4 + 4 + 4 + 4 + 4$ or $20 = 5 + 5 + 5 + 5$

$40 = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4$ or $40 = 4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5$ or $40 = 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5$

Of course, the order of $4$ and $5$ does not matter; what matters is how many of each you use.

Given a positive integer $n$, ask how many ways there are to form $n$ using $4$ and $5$.

Input Format

One line containing an integer $n$, which is the number to be formed.

Output Format

One line containing the number of ways. If this number cannot be formed, output $0$.

14

1

40

3

6

0

Hint

For $20\%$ of the testdata: $1 \le n \le 10$.

For another $15\%$ of the testdata: $1 \le n \le 10^5$, and it is guaranteed that $n \equiv 0 \pmod 4$.

For another $15\%$ of the testdata: $1 \le n \le 10^5$, and it is guaranteed that $n \equiv 0 \pmod 5$.

For $100\%$ of the testdata: $1 \le n \le 10^6$.

Translated by ChatGPT 5