Number of Multisets

There are A numbers, each between 1 and T inclusive. The same value may appear more than once.

For an integer K, choose exactly K of the given numbers and treat choices that differ only by the order of the selected elements as the same. A value may be chosen multiple times, but not more times than it appears in the input.

Compute the total number of different choices over all K satisfying S ≤ K ≤ B.

The word set in this problem does not mean a mathematical set that forbids duplicates. The important rule is that order does not matter. Two choices are the same when every value is selected the same number of times in both choices.

The first line contains four integers T, A, S, and B. The second line contains A numbers in order.

Print the number of possible sets modulo 1,000,000.

• 1 ≤ T ≤ 200
• 1 ≤ A ≤ 4000
• 1 ≤ S ≤ B ≤ A