408031: GYM102964 E Krosh and expected value problem

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.

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 answer modulo $$$10^9+7$$$. Answer can be represented as $$$P/Q$$$, where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q > 0$$$. Output $$$P * Q^{-1}$$$ modulo $$$10^9+7$$$.

5 4 2
1 2 3 4 4

13