#716 Shirogane Wants to Sing

Statement

Statement language

Shirogane and Fujiwara are practicing a song together. Fujiwara has written down the pitches of the song in order. They are given as a sequence of nonnegative integers $A=[A_1,A_2,\cdots,A_N]$ of length $N$ , where the $i$ -th note has pitch $A_i$ .

Let the pitches actually sung by Shirogane be a sequence of nonnegative integers $B=[B_1,B_2,\cdots,B_N]$ . The first pitch must be . However, Shirogane cannot change the pitch too much between consecutive notes. Therefore, for every , the following condition must hold:

|B_i-B_{i+1}|\le K

Define the error on the $i$ -th note as $|A_i-B_i|$ . The total error of the whole song is

\sum_{i=1}^{N}|A_i-B_i|.

This total error must be at most $E$ .

Find the number of integer sequences $B$ satisfying all conditions. Since the answer can be very large, print it modulo $1\,000\,000\,007$ .

Input

The input is given from Standard Input in the following format:

$N\ K\ E$ $A_1\ A_2\ \cdots\ A_N$

Output

Print the number of integer sequences $B$ satisfying all conditions, modulo $1\,000\,000\,007$ .

Constraints

$2\le N\le 100$ .
$0\le K\le 20$ .
$0\le E\le 50$ .

Subtasks

#	Score	Constraints
1	8	$K=0$ .
2	18	$N\le6$ . $E\le5$ .

Samples

Sample 1

Input

3 1 2
0 1 0

Output

5

The five valid sequences are $[0,0,0]$ , $[0,0,1]$ , $[0,1,0]$ , , and .