### Problem Statement

In a Las Vegas casino, a new type of six-sided die is being introduced. These dice may have any positive integers written its sides, but no two sides of the same die can contain the same number. For each die, the casino owner wants the mean value of the numbers written on its sides to not exceed M.

Compute the total number of allowed dice. Two dice are considered different if one can't be obtained from the other using rotations. Since the resulting number may be quite large, return it modulo 1000000007.

### Definition

 Class: CustomDice Method: countDice Parameters: int Returns: int Method signature: int countDice(int M) (be sure your method is public)

### Constraints

-M will be between 1 and 1000000, inclusive.

### Examples

0)

 `3`
`Returns: 0`
 The die with the smallest possible mean is {1,2,3,4,5,6}. Its mean is 3.5, which is greater than M=3.
1)

 `4`
`Returns: 210`
 There are 30 different dice with numbers {1,2,3,4,5,6} on their sides, they each have a mean of 3.5. There are 30 different dice with numbers {1,2,3,4,5,7} on their sides, they each have a mean of 22/6=3.(6). There are 60 different dice with {1,2,3,4,5,8} or {1,2,3,4,6,7} on their sides, they each have a mean of 23/6=3.8(3). There are 90 different dice with {1,2,3,4,5,9}, {1,2,3,4,6,8} or {1,2,3,5,6,7} on their sides, they each have a mean of 24/6=4.
2)

 `10`
`Returns: 863010`
3)

 `50`
`Returns: 375588112`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9904

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13507&pm=9904

xOberon

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky , zhuzeyuan

#### Problem categories:

Dynamic Programming