[CSES] Dice Combinations

2021-12-08

0 minute read

Algorithm

cses

Bit Strings

Task:

Your task is to count 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$.

For example, if $n=3$, there are $4$ ways:

$1+1+1$
$1+2$
$2+1$
$3$

Input

The only input line has an integer $n$.

Output

Print the number of ways modulo $10^9+7$.

Constraints

$1 \le n \le 10^6$

Example

Input:
3

Output:
4

Solutions:

Intuition:

It's prime dynamic example.

Implementation:

1        def helper(n):
2        return pow(2,n,int(1e9+7))
3        a=int(input())
4        print(helper(a))
5

Analysis:

Time complexity: $O(1)$

Space complexity: $O(1)$