Problem Statement

Your task is to calculate the number of ways to get a sum n by throwing dice. Each throw yields an integer between 1...6. For example, if n = 10 , some possible ways are 3 + 3 + 4, 1 + 4 + 1 + 4 and 1 + 1 + 6 + 1 + 1. Input Format: The only input line contains an integer n . Constraints 1 ≤ n ≤ 10 18 Output Format: Print the number of ways modulo 10 9 + 7. Examples: Example 1: Input: 1 Output: 1