Combination Sum

Given the target value N and an array of allowed positive numbers, you are asked to count the ways to write N as the sum of those numbers.

So, if the allowed values are for instance [1, 2, 3], and the number N is 4, we can sum those numbers up in 7 different ways:

All the 7 ways to sum up 1, 2, 3 to obtain 4

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

This is a classic dynamic programming problem, which can be solved by keeping a state d[sum] which represents all the possible ways to obtain the sum by combining the allowed numbers:

N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = all the combinations that sum up to `i`
d[0] = 1                   # There is 1 way to get a 0 - not to take any numbers

for i in range(1, N + 1):  # Try to obtain all the numbers sequentially 1...N
    for num in nums:       # Try to get `d[i]` with the help of `num`
        if i - num >= 0:   # If it's possible to obtain `i` from `num`
            d[i] += d[i - num]
print(d[N])

So, our state d[i] is the number of ways we can obtain i using the allowed numbers nums. We initialize everything with 0 except d[0] which we set to 1 as we can obtain 0 in only 1 way - by not using any of the allowed numbers. For all the other numbers, we look at all the possible ways we can obtain the numbers using nums.

If we can obtain the number 11 (d[11]) with let’s say 5 different ways and we know that we were able to obtain the number 8 (d[8]) with 3 different ways, then in case there is 3 in the nums array, we can obtain the number 11 with all the ways we’ve found so far + all the ways we could obtain 8 (d[8]) and then put the number 3 next to it.

Let’s simulate the algorithm on the sample input:

nums = [1, 2, 3] and N = 4

d = [1, 0, 0, 0, 0] → 1 way to obtain 0 and the rest are 0s

i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0

i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0

i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]

i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]

print(d[4]) → prints 7

Challenge - Dice Combinations

If you throw a die, it produces a number from 1 to 6. You are asked to compute the number of ways to obtain the number n by summing up together dice rolls.

Input

The input contains a single integer n (1 ≤ n ≤ ).

Output

The program should print the number of ways you can throw a die to obtain the number n as a sum of those throws. As the answer can get very large, you are asked to print it modulo .

Examples

Input	Output
2	2
3	4

Explanation

2 → 1 + 1, 2

3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB