题目描述

丽丽某天邀请小马到家里玩积木，小马可是个搭积木高手，所以丽丽想考考他。丽丽家有m(2<=m<=600000)块长方形的积木，想要让小马搭一个m层的宝塔，搭建要求如下：如果积木a在积木b上面，那么a不能比b的长度+s要长，否则容易倒。想问问你小马有多少种搭建方法,方法数可能会很大，答案 mod 1000000009的值.

输入格式：

第一行： m，s 第二行： m个数，表示每块积木的长度。

输出格式：

方法数，输出要mod 1000000009

输入样例#1：

4 1
1 2 3 100

输出样例#1：

4