Counting Coin Combinations

This problem asks you to count the number of ways to form a given sum S using coins with denominations \(1, 5, 10,\) and \(25\). You may use an unlimited number of coins of each denomination. The order in which coins are chosen does not matter.

The mathematical formulation of the problem is:

Given a target sum \(S\), find the number of solutions to the equation \[ dp[S] = \sum_{coin \in \{1,5,10,25\}} dp[S - coin] \] with the base case \(dp[0] = 1\).

For example, when \(S = 12\), the answer is 4.

inputFormat

The input consists of a single integer \(S\) (\(0 \le S \le 10^4\)) representing the target sum. The input is provided via standard input.

outputFormat

Output a single integer which is the number of ways to form the sum \(S\) using coins of denominations \(1, 5, 10,\) and \(25\). The result should be printed to standard output.

12

4