BZPRO
#2013. [Ceoi2010]A huge tower
内存限制：259 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
有N(2<=N<=620000)快砖，要搭一个N层的塔，要求：如果砖A在砖B上面，那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值
输入格式
第一行： N，D 第二行： N个数，表示每块砖的长度。
输出格式
方案数。输出要mod1000000009
样例
样例输入
4 1
1 2 3 100
样例输出
4
数据范围与提示
BZPRO