Chao Man is going to take part in the winter training. As his coach, you need to arrange problems for him to solve.
You have a problem list consisting of  problems. For the  problem, its difficulty is .

You need to cut the problem list into any number of nonempty problemsets.
Formally speaking, a plan that cuts the problem list into  nonempty problemsets can be described as an array  of length , where  and problemset  consists of  problem .

Suppose you have  problemsets after the cutting. You are going to feed problemset  to Chao Man at day .
Since Chao Man is a superman, he evaluates the difficulty of a problemset as the minimum difficulty of all problems it contains.

Chao Man loves variation. He has a endurance of value . If Chao Man discovers that there exists two adjacent days such that the absolute difference of the two problemsets' difficulty is less than , he will consider the winter training very boring.

You don't want to let Chao Man down. How many ways can you cut the problem list so that Chao Man will not consider the winter training very boring? Please output the answer modulo .

The input consists of:
    One line containing two integers  separated by a space.
    One line containing  integers  separated by spaces.

Output the answer modulo .

4 2
1 3 1 3

4

For sample 1, there are 4 ways of cutting that does not bored Chao Man: 
    1 3 1 3
    1|3|1 3
    1 3 1|3
    1|3|1|3

4 2
1 1 3 3

3

For sample 2, there are 3 ways:
    1 1 3 3
    1 1|3 3
    1 1 3|3

10 2
4 1 1 3 1 5 2 2 4 1

16

You may need to use fast read-in.