Słodycze

Limit pamięci: 64 MB

Jaś otrzymał w prezencie słoików z cukierkami. Każdy ze słoików zawiera inny rodzaj cukierków. (tzn. cukierki z tego samego słoika są takie same, a z różnych słoików są różne).

-ty słoik zawiera cukierków. Jaś postanowił zjeść część swoich cukierków. Chciałby zjeść co najmniej , ale nie więcej niż cukierków. Cały problem w tym, że Jaś nie może się zdecydować, ile cukierków jakiego rodzaju zjeść. Na ile różnych sposobów może to uczynić?

Zadanie

Twoje zadanie polega na napisaniu programu, który:

• wczyta ze standardowego wejścia iczbę cukierków, które są z każdym słoiku, oraz liczby i ,
• wyznaczy liczbę różnych sposobów (spełniających powyższe założenia), na jakie Jaś może wybrać cukierki do zjedzenia,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i , oddzielone pojedynczymi odstępami (, ). Każdy z kolejnych wierszy zawiera jedną liczbę całkowitą. Wiersz -szy zawiera liczbę - liczbę cukierków w -tym słoiku ().

Wyjście

Niech będzie liczbą różnych sposobów, na jakie Jaś może wybrać cukierki do zjedzenia. Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę: mod 2004 (czyli resztę z dzielenia przez 2004).

Przykład

Dla danych wejściowych:

2 1 3
3
5

poprawną odpowiedzią jest:

9

Oto lista wszystkich możliwych sposobów, w jakie Jaś może zjeść żądaną liczbę cukierków:

Autor zadania: Marcin Michalski.