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
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.
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.
10
Returns: 863010
20
Returns: 101548350
50
Returns: 375588112
100
Returns: 196717870
200
Returns: 665802632
500
Returns: 879053231
1000
Returns: 962358859
2000
Returns: 132854201
5000
Returns: 526200842
10000
Returns: 276610130
20000
Returns: 792436673
25000
Returns: 241849830
50000
Returns: 782989301
100000
Returns: 110520781
125013
Returns: 503092938
249850
Returns: 826840433
312000
Returns: 996281693
555222
Returns: 19525097
555123
Returns: 942200740
800000
Returns: 543105712
900000
Returns: 174984532
950000
Returns: 484722537
999999
Returns: 34356100
1000000
Returns: 432413968
1
Returns: 0
2
Returns: 0
5
Returns: 2700
6
Returns: 14940
7
Returns: 55320
8
Returns: 160590
9
Returns: 395280
999996
Returns: 12748786
999987
Returns: 698655835
134351
Returns: 782682397