[Ceoi2010]A huge tower

时间限制:10s      空间限制:259MB

题目描述

有N(2<=N<=620000)快砖,要搭一个N层的塔,要求:如果砖A在砖B上面,那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值


输入格式

第一行: N,D 第二行: N个数,表示每块砖的长度。


输出格式

方案数。输出要mod1000000009


样例输入

4 1
1 2 3 100

样例输出

4

提示

没有写明提示


题目来源

没有写明来源