Counting Sequences

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/65536 K (Java/Others)

Description

For a set of sequences of integers{a1,a2,a3,...an}, we define a sequence{ai1,ai2,ai3...aik}in which 1<=i1<i2<i3<...<ik<=n, as the sub-sequence of {a1,a2,a3,...an}. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence{ai1,ai2,ai3...aik},if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.

Input

Multiple test cases The first line will contain 2 integers n, d(2<=n<=100000,1<=d=<=10000000) The second line n integers, representing the suquence

Output

The number of Perfect Sub-sequences mod 9901

Sample Input

4 2 1 3 7 5

Sample Output

4

Hint

Source

2010 ACM-ICPC Multi-University Training Con

提交代码