Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

【问题描述】

有一个长度为 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 分: n8,m0,k3

11 分: n8,m6,k3

12 分: n8,m6,km

18 分: n8,m12,km

14 分: n106,m0,k100

11 分: n106,m106,k100

22 分: n106,m1018,k100