F - 設備移転
解説
/
あなたの通っている大学は、大学の設備を移転しようとしている。
それぞれの設備などが移転するのにかかる時間が与えられる。
大学にはN個の設備が存在します。
時間Tまでに移動できる設備の組み合わせのパターン数を1000000009で割ったあまりを求めてください。
ただしそれぞれのパターンは設備は少なくともM個移動しなければならないという制約を満たしてください。
入力は以下の形式で与えられる。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
パターン数を1000000009で割ったあまりを整数1行で出力してください
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
入力
N T M D_0 ・・・・ D_{N-1}D_iはi番目の設備が移動するのにかかる時間です。
制約
- 1≦N≦100
- 1≦T≦10000
- 0≦M≦N
- 1≦D_i≦100
出力
部分点
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