#716 Shirogane 想唱歌

题面

题面语言

Shirogane 和 Fujiwara 正在一起练习唱歌。Fujiwara 按顺序记录了歌曲中各个音的音高。这些信息以长度为 $N$ 的非负整数序列 $A=[A_1,A_2,\cdots,A_N]$ 给出，其中第 $i$ 个音的音高为 $A_i$ 。

用长度为 $N$ 的非负整数序列 $B=[B_1,B_2,\cdots,B_N]$ 表示 Shirogane 实际唱出的音高。第一个音必须为。但是，Shirogane 无法在相邻两个音之间大幅改变音高。因此，对所有，必须满足

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

定义第 $i$ 个音的错误程度为 $|A_i-B_i|$ 。整首歌的错误程度总和为

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

并且该值必须不超过 $E$ 。

求满足所有条件的整数序列 $B$ 的个数。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模后的结果。

输入从标准输入按以下格式给出：

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

输出满足所有条件的整数序列 $B$ 的个数对 $1\,000\,000\,007$ 取模后的结果。

#	分数	数据范围
1	8	$K=0$ 。
2	18	$N\le6$ . $E\le5$ .

样例 1

样例输入

3 1 2
0 1 0

样例输出

5

满足条件的序列共有 $5$ 个： $[0,0,0]$ 、 $[0,0,1]$ 、 $[0, 1$ 、和。