Description

“你还不来，我怎敢老去。” ——张爱玲

小K又给小W出了道难题！

小K先在纸上写下一个长度为 $n$ 的序列，序列中的每个元素的取值范围都在 $[1,k]$ 之间。

现在，小K突发奇想，想要在序列之后再加上 $m$ 个新元素，相同的，这 $m$ 个新元素的取值范围也在 $[1,k]$ 之间，从而使得本质不同的子序列个数尽量的多。小K规定，两个子序列被认为是不同的子序列，当且仅当他们的长度不同，或者至少有一个对应位置的值是不同的，这可难到了小W，别无他法，他只能来求助于你，希望你能解决这道小K给出的难题。

你的任务是输出最大的不同子序列的个数，由于答案可能非常大，请将答案对 $10^9+7$ 取模。特别的，一个空序列不被看作为一个子序列。

Input Format

第一行读入三个整数 $n,m,k$ 。

第二行读入 $n$ 个整数，描述小 $K$ 给出的初始序列。

Output Format

输出一个整数表示答案。

Sample

【输入输出样例】

simple1

2 1 3
1 3       

7

simple2

5 6 3
3 1 2 1 2

987

simple3

9 980007 7
4 7 2 1 3 3 6 6 7

608313080

【样例解释】

对于第一个样例，最优的方案是在后面填上2，此时有7种不同的子序列：$“1”，“2”，“3”，“1，3”，“1，2”，“3，2”，“1，3，2”$.

Hint

【数据范围】