Custom Dice

Time limit2sMemory limit128 MB

Summary

Count six-faced dice with distinct positive integers averaging at most M, treating rotations as identical, and print the count mod 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Jinyoung runs a casino. After losing almost all of his money to a famous blackjack expert, he decides to create a new die and try to win the money back with another game.

The die has six faces. Each face contains a positive integer, and all six integers are different. The average of the six integers written on the die must not exceed M.

Count how many different dice Jinyoung can make.

Two dice are considered the same if one can be rotated to look exactly like the other. Because the answer can be very large, print it modulo 1,000,000,007.

Input

The first line contains the integer M.

M is a positive integer with 1 <= M <= 1,000,000.

Output

Print the answer modulo 1,000,000,007.

Hint

The smallest possible die uses the numbers (1, 2, 3, 4, 5, 6), whose average is 3.5. Therefore no die has average at most 3.

Examples4

Example 1
Input
```
3
```
Expected output
```
0
```
Example 2
Input
```
4
```
Expected output
```
210
```
Example 3
Input
```
10
```
Expected output
```
863010
```
Example 4
Input
```
50
```
Expected output
```
375588112
```