AT_qupc2014_f 設備移転

[problemUrl]: https://atcoder.jp/contests/qupc2014/tasks/qupc2014_f あなたの通っている大学は、大学の設備を移転しようとしている。 それぞれの設備などが移転するのにかかる時間が与えられる。 大学には$ 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で割ったあまりを整数１行で出力してください ```

3 100 1
1 2 3
```

 ```
7
```


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

 ```
165
```
                            

N/A

N/A