【问题描述】

有一个长度为 $n$ 的序列，每个元素都在 $[1,k]$ 之间。 现在你要在序列后面再加上 $m$ 个在 $[1,k]$ 之间的元素，使得该序列的本质不同的子序列个数尽量多。 两个子序列被认为是不同的，当且仅当它们长度不同，或者至少一个对应位置的值不同。 输出最大的不同子序列个数，对 $10^9+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\le 8,m\le 0,k\le 3$。

11 分： $n\le 8,m\le 6,k\le 3$。

12 分： $n\le 8,m\le 6,k\le m$。

18 分： $n\le 8,m\le 12,k\le m$。

14 分： $n\le 10^6,m\le 0,k\le 100$。

11 分： $n\le 10^6,m\le 10^6,k\le 100$。

22 分： $n\le 10^6,m\le 10^18,k\le 100$。