Shirogane는 노래하고 싶어

Shirogane와 Fujiwara는 함께 노래 연습을 하고 있다. Fujiwara는 연습할 노래의 음정을 차례대로 정리해 두었다. 그 정보는 길이 $N$의 음이 아닌 정수 수열 $A=[A_1,A_2,\cdots,A_N]$으로 주어진다. 노래의 $i$번째 음은 $A_i$이다.

Shirogane가 실제로 부르는 음들을 길이 $N$의 음이 아닌 정수 수열 $B=[B_1,B_2,\cdots,B_N]$로 나타내자. 첫 음 은 반드시 이어야 한다. 하지만 Shirogane는 한 번 낸 음에서 다음 음으로 넘어갈 때 음정을 크게 바꾸지 못한다. 따라서 모든 에 대해 다음 조건을 만족해야 한다.

$i$번째 음에서 틀린 정도를 $|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$로 나눈 나머지를 출력한다.

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