← 返回题目列表

AtCoder · arc100_d

F. 多彩序列

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

给你整数 N, K,以及一个整数序列 A 长度 M.

一个整数序列,其中每个元素位于 1 和 K (含)据说是 多彩 当存在长度连续的子序列时 K 包含每个整数在 1 和 K (含)。

对于每个长度的彩色整数序列 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)。 这些序列的连续子序列的编号与 分别为 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