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$.