問題一覧 > 通常問題

No.1847 Good Sequence

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : 👑 potato167 / テスター : tatyam
お気に入りにしたユーザー ProblemId : 6892 / 自分の提出
問題文最終更新日: 2022-02-18 18:41:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 332 (順位表) の他の問題:

Problem Statement

You are given an integer $N$ and a sequence $K=K_1,K_2,\dots,K_M$ of $M$ elements consisting of integers between $1$ and $N$, inclusive.

A sequence $A=A_1,A_2,\dots,A_{L}$ of length $L$ satisfying the following conditions is called a good sequence.

  • For every integer $i$ satisfying $1\leq i\leq L$, $A_i$ is an integer between $1$ and $N$, inclusive.
  • There exists an $i$ such that there is a part where $K_i$ appears consecutively exactly $K_i$ times. That is, there exists a combination of integers $i,j$ satisfying all of the following 5 conditions simultaneously.
    • $1\leq i\leq M$
    • $0\leq j\leq L-K_{i}$
    • $A_j\neq K_i$ or $j=0$
    • $A_{j+K_i+1}\neq K_i$ or $j=L-K_{i}$
    • $A_{j+1}=A_{j+2}= \dots =A_{j+K_i}=K_i$

Find the total number of good sequences, modulo $(10^{9}+7)$.

Constraints

  • $1\leq L \leq 10^{18}$
  • $1\leq N \leq 10$
  • $1\leq M \leq N$
  • $1\leq K_i \leq N$
  • If $i\neq j$, then $K_i\neq K_j$
  • All inputs are integers

Input

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

Output

Output the answer modulo $(10^{9}+7)$. Print a newline at the end.

Sample

Sample 1
Input
3 2 2
1 2
Output
4

The following 4 are the good sequences. $A=(1,2,1),(1,2,2),(2,1,2),(2,2,1)$

Sample 2
Input
1234567890 10 3
1 6 7
Output
393512451

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