Competitions

# Dynamic Programming - Linear

# Dice Combinations

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

One integer **n** (**1** ≤ **n** ≤ `10`

).^{6}

#### Output

Print the number of ways modulo `10`

+ ^{9}**7**.

Input example #1

3

Output example #1

4