Radio

Problem 1: Radio Towers
=======================

Bessy is placing two radio towers in the mountain range near Farmer
John's farms. In order to get the best transmission, the radio towers
need to be within certain distances horizontally and vertically.

Bessy has measured out the height of the mountain range at 1-meter intervals.
She has N measurements (1 <= N <= 10^5). She needs the horizontal distance
between towers to be less than or equal to W (1 <= W < N) and the vertical
distance to be less than or equal to H (1 <= H <= 10^5).

The horizontal distance between a tower at position i and a tower at position
j is |i - j|. The vertical distance is |h_i - h_j|.

Find the number of ways to place the two _indistinguishable_ towers while
staying within the specified horizontal and vertical distances. Since this
number could be very large, output the answer modulo 1000007.

In test cases worth 50% of the points, h_i will be nondecreasing.

PROBLEM NAME: radio

INPUT
-----
* Line 1: The number of heights, N, the maximum width, W, and maximum
    height, H.
* Line 2..1+N: Line i+1 contains h_i (1 <= h_i <= 10^5), height of peak i.

SAMPLE INPUT (file radio.in)
----------------------------
5 2 2
1
3
4
5
8

OUTPUT
------
* Line 1: The number of valid ways to position the towers.

SAMPLE OUTPUT (file radio.out)
------------------------------
5