사탕

존이 사탕이 든 병 $n$개를 가지고 있다. 각 병에는 서로 다른 종류의 사탕이 들어 있다(같은 병에 든 사탕은 모두 같은 종류이고, 다른 병에 든 사탕은 서로 다른 종류이다). $i$번째 병에는 사탕이 $m_i$개 들어 있다.

존은 사탕을 전부 합쳐 $a$개 이상 $b$개 이하로 먹으려고 한다. 각 병에서는 $0$개부터 $m_i$개까지 원하는 만큼 꺼내 먹을 수 있다. 어느 한 병에서라도 꺼낸 사탕의 개수가 다르면 서로 다른 방법으로 센다.

먹는 사탕의 총 개수가 $a$개 이상 $b$개 이하가 되도록 사탕을 고르는 방법의 수를 구하여라. 이 값이 매우 커질 수 있으므로 $2004$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $n$, $a$, $b$가 공백 하나로 구분되어 주어진다($1 \le n \le 10$, $0 \le a \le b \le 10^7$). 다음 $n$개의 줄에는 정수가 하나씩 주어지며, $i+1$번째 줄에는 $i$번째 병에 든 사탕의 개수 $m_i$가 주어진다($0 \le m_i \le 10^6$).

존이 사탕을 고를 수 있는 방법의 수를 $k$라고 하자. 첫째 줄에 정수 하나 $k \bmod 2004$($k$를 $2004$로 나눈 나머지)를 출력한다.

예제에서 두 병에는 각각 $3$개와 $5$개의 사탕이 들어 있고, 먹는 총 개수는 $1$개 이상 $3$개 이하여야 한다. 각 방법을 (1번 병에서 꺼낸 개수, 2번 병에서 꺼낸 개수)로 나타내면, 유효한 $9$가지 방법은 다음과 같다.

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