Contest Duration: - (local time) (200 minutes)
E - Enormous Atcoder Railroad /

Time Limit: 1 sec / Memory Limit: 512 MB

Max Score: 1000 Points

### Problem Statement

There are N + 1 stations numbered 0, 1, 2, ..., N along a railway.
Currently, two kinds of train are operated, local and express.
A local train stops at every station, and it takes one minute from station i to i + 1, and vice versa.
An express train only stops at station S_0, S_1, S_2, ..., S_{K-1} (0 = S_0 < S_1 < S_2 < ... < S_{K-1} = N). It takes one minute from station S_i to S_{i + 1}, and vice versa.
But the president of Atcoder Railroad, Semiexp said it is not very convenient so he planned to operate one more kind of train, "semi-express".
The stations where the semi-express stops (This is T_0, T_1, T_2, ..., T_{L-1}, 0 = T_0 < T_1 < T_2 < ... < T_{L-1} = N) have to follow following conditions:
From station T_i to T_{i+1} takes 1 minutes, and vice versa.
• The center of Atcoder Kingdom is station 0, and you have to be able to go to station i atmost X minutes.
• If the express stops at the station, semi-express should stops at the station.
Print the number of ways of the set of the station where semi-express stops (sequence T).
Since the answer can be large, print the number modulo 10^9 + 7.

### Input Format

N K X
S_0 S_1 S_2 ... S_{K-1}


### Output Format

Print the number of ways of the set of the station where semi-express stops, mod 10^9 + 7 in one line.
Print \n (line break) in the end.

### Constraints

• 2 ≤ K ≤ 2500.
• 1 ≤ X ≤ 2500.
• S_0 = 0, S_{K-1} = N.
• 1 ≤ S_{i + 1} - S_i ≤ 10000.

### Scoring

• N, K, X ≤ 15.
• K, X ≤ 15.
• S_{i + 1} - S_i ≤ 15.
• K, X ≤ 40.
• S_{i + 1} - S_i ≤ 40.
• K, X ≤ 300.
• S_{i + 1} - S_i ≤ 300.
• There are no additional constraints.

### Sample Input 1

7 2 3
0 7


### Sample Output 1

55

The set of trains that stops station 0 and 7, and can't satisfy the condition is:
[0, 7], [0, 1, 7], [0, 1, 2, 7], [0, 1, 6, 7], [0, 1, 2, 6, 7], [0, 1, 2, 3, 6, 7], [0, 1, 2, 5, 6, 7], [0, 1, 2, 3, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7], 9 ways.
Therefore, the number of ways is 2^6 - 9 = 55.

### 問題文

Atcoder国には、「Atcoder鉄道」という鉄道会社がある。
これは、駅 0 から駅 N までの N + 1 個の駅で成り立っており、一直線上に並んでいる。

しかし、これだけでは足りないと思ったAtcoder鉄道の社長であるsemiexpさんは、新たに「準急列車」というものを作ろうと計画した。

ただし、その場合は駅 T_iT_{i + 1} の間を1分で走行するものとする。(両方向に行ける)
• Atcoder国の中心地は駅0なので、普通、急行、準急を最適に使うことによって駅0から乗車時間 X 分以内ですべての街にたどり着けるようにしたい。
• 急行列車の停車する駅は、必ず準急列車が停車しなければならない。
そのとき、準急列車が停車する駅の組み合わせの個数を求めなさい。
ただし、こたえが大きくなる可能性があるので、10^9 + 7 で割った余りを求めなさい。

### 入力

N K X
S_0 S_1 S_2 ... S_{K-1}


### 制約

• 2 ≤ K ≤ 2500.
• 1 ≤ X ≤ 2500.
• S_0 = 0, S_{K-1} = N.
• 1 ≤ S_{i + 1} - S_i ≤ 10000.

### 得点

• N, K, X ≤ 15.

• K, X ≤ 15
• .
• S_{i + 1} - S_i ≤ 15.

• K, X ≤ 40.
• S_{i + 1} - S_i40.

• K, X ≤ 300.
• S_{i + 1} - S_i ≤ 300.

• 追加の制約はない。

### 入力例1

7 2 3
0 7


### 出力例1

55


よって、合計で 2^6 - 9 = 55 個となります。