题目描述

输入格式

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

输出格式

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

7 2 3
0 7

55

提示

制約

• $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$ 点]

• 追加の制約はない。

Sample Explanation 1

目的を達成できない駅の集合は、$ [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$ 個となります。