E. Krosh and expected value problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Krosh has been learning probability theory and came up with the following problem: consider an array of $$$n$$$ natural numbers from $$$1$$$ to $$$x$$$ and natural number $$$k$$$. Then $$$k$$$ steps follow, on each step we take current array and simultaneously insert a random number from $$$1$$$ to $$$x$$$ between every pair of adjacent numbers, these numbers are chosen equiprobably and independently on each step and in each step. Krosh is interested what is expected number of segments consisting of the equal numbers after $$$k$$$ steps of the algorithm? For example, if $$$a = [1, 2, 4, 1, 1, 5, 5, 6]$$$, $$$x = 6$$$, then number of segments is $$$6$$$. After one step we can obtain the array: $$$[1, 5, 2, 2, 4, 3, 1, 1, 1, 1, 5, 6, 5, 2, 6]$$$ with $$$11$$$ segments.

Input

In first line you are given three natural numbers $$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^9$$$, $$$0 \le k \le 10^9$$$. In next line you are given an array of $$$n$$$ natural numbers from $$$1$$$ to $$$x$$$.

Output

Output answer modulo $$$10^9+7$$$. Answer can be represented as $$$P/Q$$$, where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q \gt 0$$$. Output $$$P * Q^{-1}$$$ modulo $$$10^9+7$$$.

Example
Input
5 4 2
1 2 3 4 4
Output
13