Background

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

Description

小 K 又给小 W 出了道难题！
小 K 先在纸上写下一个长度为 n 的序列，序列中的每个元素的取值范围都在[1,k]之间。现在，小 K 突发奇想，想要在序列之后再加上 m 个新元素，相同的，这 m 个新元素的取值范围也在[1,k]之间，从而使得本质不同的子序列个数尽量的多。小 K 规定，两个子序列被认为是不同的子序列，当且仅当他们的长度不同，或者至少有一个对应位置的值是不同的，这可难到了小 W，别无他法，他只能来求助于你，希望你能解决这道小 K 给出的难题。
你的任务是输出最大的不同子序列的个数，由于答案可能非常大，请将答案对 10^9+7 取模。特别的，一个空序列不被看作为一个子序列。

Format

Input

第一行读入三个整数 n,m,k。
第二行读入 n 个整数，描述小 K 给出的初始序列。

Output

输出一个整数表示答案。

Sample 1

Input

2 1 3
1 3

Output

7

Sample 2

Input

5 6 3
3 1 2 1

Output

987

Sample 3

Input

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

Output

608313080

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

Limitation

1s, 512MiB for each test case.
【数据范围】