Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_25_08 - Tłumacze

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 bi 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ść bi 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)

Dodane przez:Maciej Boniecki
Data dodania:2015-11-05
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.