P8395 [CCC 2022 S1] Good Fours and Good Fives

$\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$.

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

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

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