F - Colorful Sequences

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100

問題文

整数 NK、そして長さ 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