There is a railroad company in Atcoder Kingdom, "Atcoder Railroad".
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
NKXS_0S_1S_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
Subtask 1 [120 points]
N, K, X ≤ 15.
Subtask 2 [90 points]
K, X ≤ 15.
S_{i + 1} - S_i ≤ 15.
Subtask 3 [260 points]
K, X ≤ 40.
S_{i + 1} - S_i ≤ 40.
Subtask 4 [160 points]
K, X ≤ 300.
S_{i + 1} - S_i ≤ 300.
Subtask 5 [370 points]
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.