[CEOI2004] Sweets

题目描述

John 得到了 $n$ 罐糖果。不同的糖果罐,糖果的种类不同(即同一个糖果罐里的糖果种类是相同的,不同的糖果罐里的糖果的种类是不同的)。第 $i$ 个糖果罐里有 $m_{i}$ 个糖果。John 决定吃掉一些糖果,他想吃掉至少 $a$ 个糖果,但不超过 $b$ 个。问题是 John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢?

输入输出格式

输入格式


输入共 $n+1$ 行: 第一行读入 $n$,$a$,$b$。 接下来 $n$ 行,一行一个数,代表 $m_{i}$。

输出格式


仅一行,表示 John 能够选择的满足以上条件的吃掉糖果的方法数,答案对 $2004$ 取模。

输入输出样例

输入样例 #1

2 1 3
3
5

输出样例 #1

9

说明

#### 数据范围及限制 对于 $100\%$ 的数据,保证 $1\leq n \leq 10$,$0\leq a \leq b \leq 10^7$,$0 \leq m_{i} \leq 10^6$。 #### 说明 本题译自 [Central European Olympiad in Informatics 2004](https://www.oi.edu.pl/old/php/ceoi2004.php?module=show&file=news) [Day 1](https://www.oi.edu.pl/old/php/ceoi2004.php?module=show&file=tasks) [T2 Sweets](https://www.oi.edu.pl/old/ceoi2004/problems/swe.pdf)。