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

• The only input line contains an integer \(n\).

Output

• Print the number of ways modulo \(10^9+7\).

Constraints

• \(1\leq n\leq 10^{18}\)

Example

Sample input

8

Sample output

125