問題一覧 > 通常問題

No.1847 Good Sequence

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : 👑 potato167potato167 / テスター : 👑 tatyamtatyam
0 ProblemId : 6892 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-18 18:41:19

問題文

整数 $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)$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 2 2
1 2
出力
4

以下の 4 つがいい数列です。 $A=(1,2,1),(1,2,2),(2,1,2),(2,2,1)$

サンプル2
入力
1234567890 10 3
1 6 7
出力
393512451

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。