> [!Question] Problem
>**Input**: The only input line has an integer $n.$
>
>**Output**: the number of ways to construct sum $n$ by throwing a dice one or more times. Each throw produces an outcome between $1$ and $6$ modulo $10^{9}+7$.
>
>**Constraints**: $1 \leq n\leq 10^{6}$
###### Solution
Let $T(n)$ denote the number of ways to construct $n$ by throwing a dice zero or more times. Then $T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)+T(n-5)+T(n-6)$ since each construction must end with either $1,2,\dots,6$ and for each $i = 1,\dots, 6$ the number of constructions of $n$ that end with $i$ equals the number of constructions of $n-i.$
Base case: $T(n) =0$ for $n<0$ and $T(0)=1$ (zero throws of the dice).
These follow trivially from [[Coin Combinations I]] solution.
Python implementation using [[Memoization|memoization]]:
```run-python
md = 10**9 + 7
maxN = 10**6
#n = input()
n = 10**6
dp = [0]*(maxN+1); dp[0] = 1
for i in range(1, n+1):
s = 0; j = 1;
while (i-j >= 0 and j <= 6):
s += dp[i-j]; j += 1
dp[i] = s % md
print(dp[n])
```