F - 設備移転 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

あなたの通っている大学は、大学の設備を移転しようとしている。
それぞれの設備などが移転するのにかかる時間が与えられる。

大学にはN個の設備が存在します。
時間Tまでに移動できる設備の組み合わせのパターン数を1000000009で割ったあまりを求めてください。
ただしそれぞれのパターンは設備は少なくともM個移動しなければならないという制約を満たしてください。

入力

入力は以下の形式で与えられる。 
N T M
D_0 ・・・・ D_{N-1}
D_iはi番目の設備が移動するのにかかる時間です。

制約

入力中は各変数はすべて整数である。また、以下の制約を満たす。
  • 1≦N≦100
  • 1≦T≦10000
  • 0≦M≦N
  • 1≦D_i≦100

出力

パターン数を1000000009で割ったあまりを整数１行で出力してください

部分点

M=0であるいくつかのテストケースに正答すると、 60点を得ることができる。

入力例 1

3 100 1
1 2 3

出力例 1

7

入力例 2

10 3 2
1 1 1 1 1 1 1 1 1 1

出力例 2

165