Counting Ways to Sum with 4 and 5

Finn loves the numbers \(4\) and \(5\). He believes that every positive integer \(n\) can be represented as a sum of several \(4\)s and \(5\)s. In this problem, given a positive integer \(n\), your task is to compute the number of ways to write \(n = 4a + 5b\) where \(a, b \ge 0\). The order of summands does not matter, only the counts of \(4\)s and \(5\)s are important.

For example:

• \(14 = 5+5+4\) → 1 way
• \(20 = 4+4+4+4+4\) or \(20 = 5+5+5+5\) → 2 ways
• \(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\) → 3 ways

inputFormat

The input consists of a single line containing a positive integer \(n\) (\(1 \leq n \leq 10^9\)).

outputFormat

Output a single integer, the number of ways to represent \(n\) as \(n=4a+5b\) with non-negative integers \(a\) and \(b\).

sample

14

1