【问题描述】
有一个长度为 n 的序列,每个元素都在 [1,k] 之间。 现在你要在序列后面再加上 m 个在 [1,k] 之间的元素,使得该序列的本质不同的子序列个数尽量多。 两个子序列被认为是不同的,当且仅当它们长度不同,或者至少一个对应位置的值不同。 输出最大的不同子序列个数,对 109+7 取模。注意空序列不被看作一个子序列。
【输入格式】 从文件 sequence.in 中读入数据。 第一行三个整数 n,m,k。 第二行 n 个整数描述初始序列。
【输出格式】 输出到文件 sequence.out 中。 输出一个整数表示答案。
2 1 3
1 3
7
5 6 3
3 1 2 1 2
987
9 980007 7
4 7 2 1 3 3 6 6 7
608313080
【数据范围】
12 分: n≤8,m≤0,k≤3。
11 分: n≤8,m≤6,k≤3。
12 分: n≤8,m≤6,k≤m。
18 分: n≤8,m≤12,k≤m。
14 分: n≤106,m≤0,k≤100。
11 分: n≤106,m≤106,k≤100。
22 分: n≤106,m≤1018,k≤100。