description

一个长为n的序列，每个元素都在\([1,k]\)之间。现在小C想在序列后面再加上\(m\)个\([1,k]\)之内的元素，使得本质不同的子序列个数尽量多。两个子序列被认为是不同的，当且仅当它们长度不同，或者至少一个对应位置的值不同。输出最大的不同子序列个数，对\(10^9 + 7\)取模。注意空序列不被看作一个子序列。

input

第一行三个整数\(n, m, k\)。
第二行\(n\)个整数描述初始序列。

output

输出一个整数表示答案.

sample input

2 1 3
1 3

sample output

7

limitations