← 返回题目列表

AtCoder · qupc2014_f

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取余的结果,作为一行整数。

部分点

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