設備移転
题意翻译
你所就读的大学，想要搬迁大学的设备。每个设备的搬迁都需要一定的时间。
大学里有N个设备，移动时间为T。求移动设备的方案数。
需要满足至少M个设备被移动了。
# 输入格式：
第一行 N，T，M
第二行 D1，D2，D3...DN
Di是指第i设备移动所需的时间。
# 输出格式：
一行，即能移动的方案数（请大家自觉养成做岛国题要换行的好习惯）。
答案对100000009（10e+9）取模。
题目描述
[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で割ったあまりを整数１行で出力してください ```
<pre class="prettyprint linenums">
3 100 1
1 2 3
```
```
<pre class="prettyprint linenums">
7
```
```
<pre class="prettyprint linenums">
10 3 2
1 1 1 1 1 1 1 1 1 1
```
```
<pre class="prettyprint linenums">
165
```