IE1 - Sweets

no tags 

John has got n jars with candies. Each of the jars contains a different kind of candies (i.e. candies from the same jar are of the same kind, and candies from different jars are of different kinds). The i-th jar contains mi candies. John has decided to eat some of his candies. He would like to eat at least a of them but no more than b. The problem is that John can't decide how many candies and of what kinds he would like to eat. In how many ways can he do it?

Input

The first line of input contains three integers: n, a and b, separated by single spaces (1 ≤ n ≤ 10, 0 a b ≤ 10000000). Each of the following n lines contains one integer. Line i+1 contains integer mi - the amount of candies in the i-th jar (0 mi ≤ 1000000).

Output

Let k be the number of different ways John can choose the candies to be eaten. The first and only line of output should contain one integer: k mod 2004 (i.e. the remainder of k divided by 2004).

Example

Input:
2 1 3
3
5
Output:
9
John can choose candies in the following ways: (1,0), (2,0), (3,0), (0,1), (0,2), (0,3), (1,1), (1,2), (2,1)


Added by:acheron
Date:2013-10-19
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CEOI 2004