Max Score: 1000 Points

Problem Statement

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

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

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.