子序列的个数

对于一个子序列，我们考虑增加一个x到子序列末尾对子序列个数的影响
我们定义以i结尾的子序列个数为f(x)
可以发现，如果我们在子序列末尾增加一个x，会对f(x)的值进行更新，由于当前追加i到末尾的子序列个数
为 f(i)，即无论我们追加的是什么字符，f(x)变成的值是一样的 即子序列个数等于sum+1,显然每次取最小的f(x)是最优的，因为这样迭代速度最快，所以这其实是一个循环矩阵，取最久未被访问的x一定是最优的

不同子序列个数可以O（N）dp计算

——
——
——
——
链接：https://ac.nowcoder.com/acm/contest/11168/F
来源：牛客网

题目描述
有一个长度为 n 的整数序列，序列中的元素都从 [1,k] 中选择 。
现在你要将这个序列的长度扩充到 n+m ，即你需要从 [1,k] 中选择一些数填充到原序列的后面 m 位 。
你需要求出扩充后的序列的不同子序列的数量的最大值对 10^9+7 取模后的值 。
输入描述:
第一行三个整数 n，m，k 。
第二行 n 个正整数表示原序列 。
输出描述:
一个正整数表示答案对 10^9+7 取模后的值 。
示例1
输入
复制
2 1 3
1 2
输出
复制
7