Coin Change: Count Ways to Make Change

You are given an integer n representing an amount in cents. Your task is to determine the number of ways to make change for n using coins of denominations 1, 2, and 5 cents. There is exactly one way to produce 0 cents (by using no coins).

The solution should handle negative values by outputting 0 ways.

One can express the recurrence as: $$dp[i] = \sum_{coin \in \{1, 2, 5\}} dp[i - coin]$$ for all \(i \geq coin\), with the base condition \(dp[0]=1\).

inputFormat

A single line containing an integer n which represents the amount in cents. The input is read from standard input (stdin).

outputFormat

A single integer denoting the number of ways to make change for n using coins with denominations 1, 2, and 5 cents. The output is printed to standard output (stdout).## sample

5

4