AlgoLiga 2018

W Krakowie n tłumaczy, na zlecenie królowej Jadwigi, przekłada na język polski Księge Psalmów. Księga Psalmów posiada s stron. Tłumacze reprezentują różny poziom, i-ty tłumacz podczas przekładu jednej strony robi dokładnie b_i błędów. Królowa Jadwiga zaakceptuje dzieło jeżeli nie będzie ono zawierało więcej niż b błędów.

Naszą bohaterkę nurtuje jedno pytanie, na ile sposobów można podzielić pracę pomiędzy tłumaczy, tak aby nie zrobili oni więcej niż b błędów? Królowa dopuszcza sytuację, w której nie wszyscy tłumacze pracują nad przekładem.

Wejście

W pierwszej linii wejścia znajdują się trzy liczby naturalne n ∈ [1;200], s ∈ [1;200] i b ∈ [1;200] oznaczające odpowiednio liczbę tłumaczy, ilość stron Księgi Psalmów oraz maksymalną dopuszczalną liczbę błędów jakie mogą zrobić autorzy przekładu. W kolejnej linii znajduje się n liczb z przedziału [0;200]. Liczba na pozycji i-tej określa wartość b_i dla i-tego tłumacza.

Wyjście

Na wyjściu należy wypisać resztę z dzielenia szukanej liczby sposobów podziału pracy przez 1000000009.

Przykład

Wejście

3 4 5
1 2 1

Wyjście

9

Wyjaśnienie

Możliwe podziały stron pomiędzy 3 tłumaczy to:

• 4 - 0 - 0 (4 błędy)
• 3 - 1 - 0 (5 błędów)
• 3 - 0 - 1 (4 błędy)
• 2 - 1 - 1 (5 błędów)
• 2 - 0 - 2 (4 błędy)
• 1 - 1 - 2 (5 błędów)
• 1 - 0 - 3 (4 błędy)
• 0 - 1 - 3 (5 błędów)
• 0 - 0 - 4 (4 błędy)