問題文

整数 $N$ と $1$ 以上 $N$ 以下の整数からなる要素数 $M$ の数列 $K=K_1,K_2,\dots,K_M$ が与えられます。

長さ $L$ の数列 $A=A_1,A_2,\dots,A_{L}$ であって、以下の条件を満たすものをいい数列と呼びます。

• $1\leq i\leq L$ を満たす任意の整数 $i$ について、 $A_i$ は $1$ 以上 $N$ 以下の整数
• $K_i$ がちょうど $K_i$ 個 並んでいる部分が存在するような $i$ が存在する。つまり、以下の 5 つを同時に満たす整数 $i,j$ の組み合わせが存在する。
  • $1\leq i\leq M$
  • $0\leq j\leq L-K_{i}$
  • $A_j\neq K_i$ もしくは $j=0$
  • $A_{j+K_i+1}\neq K_i$ もしくは $j=L-K_{i}$
  • $A_{j+1}=A_{j+2}= \dots =A_{j+K_i}=K_i$

いい数列の総数を $(10^{9}+7)$ で割ったあまりを求めてください。

制約

• $1\leq L \leq 10^{18}$
• $1\leq N \leq 10$
• $1\leq M \leq N$
• $1\leq K_i \leq N$
• $i\neq j$ ならば $K_i\neq K_j$
• 入力は全て整数

入力

$L \; N\; M$
$K_1 \; K_2 \; \cdots \;K_M$

出力

答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

3 2 2
1 2

4

1234567890 10 3
1 6 7

393512451