Sweets

John has $n$ jars of candies. Each jar holds a distinct kind of candy (all candies in one jar are of the same kind, and candies from different jars are of different kinds). The $i$-th jar contains $m_i$ candies.

John wants to eat some of his candies — at least $a$ but no more than $b$ in total. From each jar he may take any number of candies between $0$ and $m_i$ inclusive. Two ways of eating are different if they differ in the number of candies taken from at least one jar.

Count the number of ways John can choose the candies to eat so that the total eaten is at least $a$ and at most $b$. Since this number can be large, output it modulo $2004$.

The first line contains three integers $n$, $a$, and $b$ separated by single spaces ($1 \le n \le 10$, $0 \le a \le b \le 10^7$). Each of the next $n$ lines contains one integer; line $i+1$ contains $m_i$, the number of candies in the $i$-th jar ($0 \le m_i \le 10^6$).

Let $k$ be the number of ways John can choose the candies to eat. Output a single integer: $k \bmod 2004$ (the remainder of $k$ divided by $2004$).

In the sample the two jars hold $3$ and $5$ candies, and the total eaten must satisfy $1 \le \text{total} \le 3$. Writing each way as (candies taken from jar 1, candies taken from jar 2), the $9$ valid ways are:

$(1,0), (2,0), (3,0), (0,1), (0,2), (0,3), (1,1), (1,2), (2,1)$