E - Enormous Atcoder Railroad Editorial /

Time Limit: 1 sec / Memory Limit: 512 MB

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.
配点：1000 点

問題文

Atcoder国には、「Atcoder鉄道」という鉄道会社がある。
これは、駅 0 から駅 N までの N + 1 個の駅で成り立っており、一直線上に並んでいる。
普通電車はすべての駅に停車し、駅 i と i + 1 の間を1分で走行する。(両方向に行ける)
急行電車は駅 S_0, S_1, S_2,..., S_{K-1} に停車し、駅 S_i と S_{i + 1} の間を1分で走行する。（両方向に行ける)
しかし、これだけでは足りないと思ったAtcoder鉄道の社長であるsemiexpさんは、新たに「準急列車」というものを作ろうと計画した。
準急列車の停車する駅 T_0, T_1, T_2,..., T_{L-1} (L は準急電車の停車駅の個数で、0 = T_0 < T_1 < T_2 < ... < T_{L-1} = N) は、次の条件を満たすように決めることにしました。
ただし、その場合は駅 T_i と T_{i + 1} の間を1分で走行するものとする。(両方向に行ける)
  • Atcoder国の中心地は駅0なので、普通、急行、準急を最適に使うことによって駅0から乗車時間 X 分以内ですべての街にたどり着けるようにしたい。
  • 急行列車の停車する駅は、必ず準急列車が停車しなければならない。
そのとき、準急列車が停車する駅の組み合わせの個数を求めなさい。
ただし、こたえが大きくなる可能性があるので、10^9 + 7 で割った余りを求めなさい。

入力

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

出力

通り数を 10^9 + 7 で割った余りを1行に出力しなさい。
最後には改行を入れること。

制約

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

得点

小課題1 [120 点]
  • N, K, X ≤ 15.
小課題2 [90 点]
  • K, X ≤ 15
    • .
  • S_{i + 1} - S_i ≤ 15.
小課題3 [260 点]
  • K, X ≤ 40.
  • S_{i + 1} - S_i ≦ 40.
小課題4 [160 点]
  • K, X ≤ 300.
  • S_{i + 1} - S_i ≤ 300.
小課題5 [370 点]
  • 追加の制約はない。

入力例1

7 2 3
0 7

出力例1

55
目的を達成できない駅の集合は、[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 個です。
よって、合計で 2^6 - 9 = 55 個となります。