分数: 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