Count Supersequences
Contest: Codeforces Round 877 (Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, math

You are given an array $$$a$$$ of $$$n$$$ integers, where all elements $$$a_i$$$ lie in the range $$$[1, k]$$$. How many different arrays $$$b$$$ of $$$m$$$ integers, where all elements $$$b_i$$$ lie in the range $$$[1, k]$$$, contain $$$a$$$ as a subsequence? Two arrays are considered different if they differ in at least one position.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements.

Since the answer may be large, print it modulo $$$10^9 + 7$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$n \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$) — the size of $$$a$$$, the size of $$$b$$$, and the maximum value allowed in the arrays, respectively.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1\le a_i \le k$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of suitable arrays $$$b$$$, modulo $$$10^9+7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first example, since $$$k=1$$$, there is only one array of size $$$m$$$ consisting of the integers $$$[1, k]$$$. This array ($$$[1, 1, \ldots, 1]$$$) contains the original array as a subsequence, so the answer is 1.

For the second example, the $$$9$$$ arrays are $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[1, 2, 2, 3]$$$, $$$[1, 2, 3, 2]$$$, $$$[1, 3, 2, 2]$$$, $$$[2, 1, 2, 2]$$$, $$$[3, 1, 2, 2]$$$.

For the fourth example, since $$$m=n$$$, the only array of size $$$m$$$ that contains $$$a$$$ as a subsequence is $$$a$$$ itself.

Example input:
7
1 1000000 1
1
3 4 3
1 2 2
5 7 8
1 2 3 4 1
6 6 18
18 2 2 5 2 16
1 10 2
1
8 10 1234567
1 1 2 1 2 2 2 1
5 1000000000 1000000000
525785549 816356460 108064697 194447117 725595511

Example output:
1
9
1079
1
1023
906241579
232432822

Editorial:
Let's first consider a DP solution. Let $$$dp_{i,j}$$$ be the number of arrays of length $$$i$$$, such that the longest prefix of $$$a$$$ that appears as a subsequence of the array is of length $$$j$$$.
To compute this DP, consider some cases. Let $$$b'$$$ be the subarray of the first $$$i$$$ elements of $$$b$$$, and $$$a'$$$ be the subarray of the first $$$j$$$ elements of $$$a$$$.
1. Every subsequence of $$$b'$$$ that equals $$$a'$$$ includes position $$$i$$$ of $$$b'$$$: In this case, position $$$i$$$ must be part of the subsequence. This gives us $$$dp_{i-1, j-1}$$$ solutions.
2. At least one subsequence of $$$b'$$$ that equals $$$a'$$$ doesn't include position $$$i$$$, and $$$j < n$$$: In this case, the value in position $$$i$$$ can be anything except for $$$a_{j+1}$$$, because that would create a subsequence of length $$$j+1$$$. So this gives us $$$(k-1)dp_{i-1, j}$$$ solutions.
3. At least one subsequence of $$$b'$$$ that equals $$$a'$$$ doesn't include position $$$i$$$, and $$$j = n$$$: This is the same as the previous case, except we don't have a "next" element to worry about, so anything can go in position $$$i$$$, and there are $$$k\cdot dp_{i-1, j}$$$ solutions.
So the final equation for the DP comes out to
$$$$$$dp_{i,j} = \begin{cases} dp_{i-1, j-1} + (k-1)dp_{i-1, j} & j < n \\ dp_{i-1, j-1} + k\cdot dp_{i-1, j} & j = n \end{cases}$$$$$$
This would be $$$O(nm)$$$ to compute, so it will TLE. However, we can notice that the DP does not depend on $$$a$$$! This means we can change the $$$a_i$$$ values to anything we want, and it won't change the answer. To simplify the problem, let all $$$a_i = 1$$$. Now, the problem becomes, how many arrays of size $$$m$$$, consisting of the values $$$[1, k]$$$, contain at least $$$n$$$ ones?
To compute this, let's find the number of arrays of size $$$m$$$ that contain less than $$$n$$$ ones, and subtract it from $$$k^m$$$, the total number of arrays. There are $$$\binom{m}{i}(k-1)^{m-i}$$$ arrays that contain exactly $$$i$$$ ones, so the answer is
$$$$$$k^m - \sum_{i=0}^{n-1} \binom{m}{i}(k-1)^{m-i}$$$$$$
We use fast exponentiation to compute the powers of $$$k-1$$$, and to compute the $$$\binom{m}{i}$$$ values, we use the fact that $$$\binom{m}{0} = 1$$$ and for $$$i \ge 1$$$,
$$$$$$\binom{m}{i} = \frac{m(m-1)\ldots(m-i+1)}{i(i-1)\ldots 1} = \frac{m - i + 1}{i}\binom{m}{i - 1}$$$$$$
So we can compute the first $$$n$$$ $$$\binom{m}{i}$$$ values within the time limit.
Complexity: $$$O(n \log M)$$$ where $$$M = 10^9 + 7$$$.