Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2900

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Vitta, an owner of a shop selling icecream always broods over some strange ideas. Though her shop already has an overwhelming advantage over her opponents. In her shop, there are n kinds of icecream, each marked by Vitta with an integer according to the price and the loveness of the customers. (We assume there are infinite amount of icecream in each kind.) Now she wants to make them into several series which satisfy the following rules:

1. You must choose the icecream in order, and you must choose at least one kind of icecream.

2. A series contains k kinds of icecream at least.

3. The difference of given mark of every two adjoining icecream in each series must be no more than p.

Now she wants to know how many series can be formed?

The rusult may be huge, you can only output the result modulo m.


The test contains mutiple cases.

In each case, there are 4 integers in the first line, n (0 < n <= 2000), k (0 <= k <= n), p, m (m <= 1000000000) as the problem statement told.

The next line contains n nonnegative integers, the i-th integer represents the mark of the i-th icecream given by Vitta (Each mark is no more than 100).


For each case, output one line, the number of the series can be formed.

Sample Input

6 2 1 10
3 2 5 4 6 7

Sample Output


The 6 series are 3-2; 3-4; 5-4; 5-6; 5-6-7; 6-7

Author: WANG, Naiyan
Source: ZOJ Monthly, January 2008
Submit    Status