← RoseCode

ROSECODE 487

Good sequences revisited

liuguangxi · Programming ·

Let F(N,M,R,D) be the number of good sequences which meet the following condition:
(1) The sequence has N elements
(2) The maximum element in the sequence is equal to M
(3) The sequence contains R records
(4) Each number occurs no more than D times in the sequence
The good sequence and records are the same definition in Problem 474.

For example, F(4,2,2,2) is 3. Only three sequences {1,1,2,2}, {1,2,1,2}, {1,2,2,1} meet the conditions:
(1) 4 elements
(2) Maximum element = 2
(3) 2 records
(4) Each number occurs no more than 2 times
Notice {1,2,1,1} is not in F(4,2,2,2) because number 1 occurs 3 times; {2,1,2,2} is not in F(4,2,2,2) because it contains only 1 record and number 2 occurs 3 times; {2,3,1,2} is not in F(4,2,2,2) because the maximum element is 3.

You are given F(11,8,3,2)=394581 and F(20,13,7,4)mod1000000007=342894563.

Find F(80,47,13,10)mod1000000007.
Thanks to C_K_Yang for the idea.