Dice Sum Ways

You are given an integer \(N\). Your task is to calculate the number of different ways to obtain a sum exactly equal to \(N\) using an arbitrary number of throws of a fair six-sided die. Each die has faces from 1 to 6. A valid sequence of dice throws is one where the sum of the numbers on all dice is exactly \(N\).

A dynamic programming solution is ideal for this problem. Consider the recurrence: \[ \text{dp}[i] = \sum_{j=1}^{6} \text{dp}[i-j]\quad\text{for } i \ge 1, \] with the initial condition \(\text{dp}[0] = 1\) (there is one way to achieve a sum of 0: by not throwing any dice).

Try to implement an efficient solution that reads from standard input and writes the result to standard output.

inputFormat

The input consists of a single integer \(N\) (\(0 \leq N \leq 10^5\)), provided via standard input.

outputFormat

Output a single integer representing the number of ways to achieve the sum \(N\) using any number of throws of a six-sided die. The answer should be printed to standard output.

1

1