
SWEETS	Конфеты (олимпиада по информатике центрального европейского региона) CEOI, July 14, 2004 SWEETS Description 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 m, 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? Task Your task is to write a program SWEETS that: reads from the standard input the amount of candies in each of the jars, and integers a and b determines the number of ways John can choose the candies he will eat (satisfying the above conditions) writes the result to the standard output Characteristics Available memory: 64Mb Maximum running time: 0.1s Input file The first line of input file SWEETS.IN 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 m_i - the amount of candies in the i-th jar (0<=m_i<=1000000). Output file Let k be the number of different ways John can choose the candies to be eaten. The first and only line of output file SWEETS.OUT should contain one integer: k mod 2004 (i.e. the remainder of k divided by 2004). Example SWEETS.IN 2 1 3 3 5 SWEETS.OUT 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)

SWEETS

Конфеты (олимпиада по информатике центрального европейского региона)
CEOI, July 14, 2004
SWEETS

Description
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 m, 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?

Task
Your task is to write a program SWEETS that:

reads from the standard input the amount of candies in each of the jars, and integers a and b
determines the number of ways John can choose the candies he will eat (satisfying the above conditions)
writes the result to the standard output

Characteristics
Available memory: 64Mb
Maximum running time: 0.1s

Input file
The first line of input file SWEETS.IN 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 m_i - the amount of candies in the i-th jar (0<=m_i<=1000000).

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

Example

SWEETS.IN
2 1 3
3
5

SWEETS.OUT
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)