/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1100 点
問題文
整数 N と K、そして長さ M の整数列 A が与えられます。
各要素が 1 以上 K 以下の整数である整数列がカラフルであるとは、 その整数列の長さ K の連続する部分列であって、1 から K までの整数を 1 個ずつ含むものが存在することを意味します。
すべての長さ N のカラフルな整数列について、その連続する部分列であって A に一致するものの個数を数えて、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを求めてください。
制約
- 1 \leq N \leq 25000
- 1 \leq K \leq 400
- 1 \leq M \leq N
- 1 \leq A_i \leq K
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K M A_1 A_2 ... A_M
出力
すべての長さ N のカラフルな整数列について、その連続する部分列であって A に一致するものの個数を数えて、 その総和を 10^9+7 で割った余りを出力せよ。
入力例 1
3 2 1 1
出力例 1
9
長さ 3 のカラフルな整数列は、(1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1) の 6 個です。 これらの整数列の、連続する部分列であって A=(1) に一致するものの個数は、それぞれ 2, 2, 1, 2, 1, 1 個です。 よって、これらの合計である 9 が答えになります。
入力例 2
4 2 2 1 2
出力例 2
12
入力例 3
7 4 5 1 2 3 1 2
出力例 3
17
入力例 4
5 4 3 1 1 1
出力例 4
0
入力例 5
10 3 5 1 1 2 3 3
出力例 5
1458
入力例 6
25000 400 4 3 7 31 127
出力例 6
923966268
入力例 7
9954 310 12 267 193 278 294 6 63 86 166 157 193 168 43
出力例 7
979180369
Score : 1100 points
Problem Statement
You are given integers N, K, and an integer sequence A of length M.
An integer sequence where each element is between 1 and K (inclusive) is said to be colorful when there exists a contiguous subsequence of length K of the sequence that contains one occurrence of each integer between 1 and K (inclusive).
For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then find the sum of all the counts. Here, the answer can be extremely large, so find the sum modulo 10^9+7.
Constraints
- 1 \leq N \leq 25000
- 1 \leq K \leq 400
- 1 \leq M \leq N
- 1 \leq A_i \leq K
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K M A_1 A_2 ... A_M
Output
For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then print the sum of all the counts modulo 10^9+7.
Sample Input 1
3 2 1 1
Sample Output 1
9
There are six colorful sequences of length 3: (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2) and (2,2,1). The numbers of the contiguous subsequences of these sequences that coincide with A=(1) are 2, 2, 1, 2, 1 and 1, respectively. Thus, the answer is their sum, 9.
Sample Input 2
4 2 2 1 2
Sample Output 2
12
Sample Input 3
7 4 5 1 2 3 1 2
Sample Output 3
17
Sample Input 4
5 4 3 1 1 1
Sample Output 4
0
Sample Input 5
10 3 5 1 1 2 3 3
Sample Output 5
1458
Sample Input 6
25000 400 4 3 7 31 127
Sample Output 6
923966268
Sample Input 7
9954 310 12 267 193 278 294 6 63 86 166 157 193 168 43
Sample Output 7
979180369