有一个长度为 n 的整数序列，序列中的元素都从 [1,k] 中选择 。
现在你要将这个序列的长度扩充到 n+m ，即你需要从 [1,k] 中选择一些数填充到原序列的后面 m 位 。
你需要求出扩充后的序列的不同子序列的数量的最大值对 10^9+7 取模后的值 。
输入描述:
第一行三个整数 n，m，k 。
第二行 n 个正整数表示原序列 。
输出描述:
一个正整数表示答案对 10^9+7 取模后的值 。
示例1
说明
最优方案是把序列变成 1 2 3，这样不同的子序列有 7 中，分别为 [1]，[2]，[3]，[1,2]，[1,3]，[2,3]，[1,2,3] 。
备注:
n <= 10^6，m <= 10^18，k <= 100 。