Description

John received $n$ jars of sweets. Different jars contain different types of sweets (that is, all sweets in the same jar are of the same type, and different jars contain different types). The $i$-th jar contains $m_i$ sweets. John decides to eat some sweets: he wants to eat at least $a$ sweets, but no more than $b$ sweets. The problem is that John cannot decide how many sweets to eat in total, or how many of each type to eat. How many different ways are there to do this?

Input Format

The input contains $n+1$ lines:

The first line contains $n$, $a$, $b$.

The next $n$ lines each contain one integer, representing $m_i$.

Output Format

Print one line: the number of ways John can choose to eat sweets satisfying the conditions above, modulo $2004$.

2 1 3
3
5

9

Hint

Constraints and Limits

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10$, $0 \leq a \leq b \leq 10^7$, and $0 \leq m_i \leq 10^6$.

Notes

This problem is translated from Central European Olympiad in Informatics 2004 Day 1 T2 Sweets。

Translated by ChatGPT 5