Count Supersequences
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$$$.
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.
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$$$.
For each test case, output a single integer — the number of suitable arrays $$$b$$$, modulo $$$10^9+7$$$.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def pow(x, y, mod):
    if x == -1:
        return 1 - y % 2 * 2
    (ans, u) = (1, x)
    while y:
        if y & 1:
            ans = ans * u % mod
        y >>= 1
        u = u * u % mod
    return ans
t = int(input())
mod = 10 ** 9 + 7
ans = []
for _ in range(t):
    (n, m, k) = map(int, input().split())
    a = list(map(int, input().split()))
    (u, v, w) = (1, 1, pow(k - 1, m, mod))
    inv = pow(k - 1, mod - 2, mod)
    ng = 0
    for i in range(n):
        ng += u * pow(v, mod - 2, mod) % mod * w % mod
        (u, v, w) = (u * (m - i) % mod, v * (i + 1) % mod, w * inv % mod)
    ans0 = (pow(k, m, mod) - ng) % mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))
import sys
import math
import heapq
import bisect
from collections import Counter, defaultdict, deque
from io import BytesIO, IOBase
from types import GeneratorType
import string

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split(' ')))

def get_int_grid(n):
    return [get_ints() for _ in range(n)]

def get_str():
    return input().strip()

def get_strs():
    return get_str().split(' ')

def yes_no(b):
    if b:
        return 'YES'
    else:
        return 'NO'

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def binary_search(good, left, right, delta=1, right_true=False):
    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))
M = 10 ** 9 + 7
facts = [1]
nmax = 4 * 10 ** 5
for i in range(1, nmax + 1):
    facts.append(facts[-1] * i % M)

def inv_mod(a, M):
    """"""
    return pow(a, M - 2, M)
invfacts = [inv_mod(facts[-1], M)]
for i in range(nmax, 0, -1):
    invfacts.append(invfacts[-1] * i % M)
invfacts = invfacts[::-1]
invnums = [None] * nmax
for i in range(1, nmax):
    invnums[i] = invfacts[i] * facts[i - 1] % M

def solve_e():
    (n, m, k) = get_ints()
    a = get_ints()
    if k == 1:
        return 1
    mcj = [1]
    nmax = 4 * 10 ** 5
    powsmj = [pow(k - 1, m - n + 1, M)]
    for i in range(1, n):
        new = mcj[-1] * (m - i + 1)
        new %= M
        new *= invnums[i]
        new %= M
        mcj.append(new)
        powsmj.append(powsmj[-1] * (k - 1) % M)
    powsmj = powsmj[::-1]
    S = pow(k, m, M)
    for j in range(n):
        tmp = mcj[j] * powsmj[j]
        S -= tmp
        S %= M
    return S
t = get_int()
for _ in range(t):
    print(solve_e())
import sys
input = sys.stdin.readline

class Factorial:

    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod
t = int(input())
mod = 10 ** 9 + 7
fact = Factorial(2 * 10 ** 5 + 1, mod)
for _ in range(t):
    (n, m, k) = map(int, input().split())
    input()
    if k == 1:
        print(1)
    else:
        ans = pow(k, m, mod)
        k_inv = pow(k - 1, mod - 2, mod)
        k_pow = pow(k - 1, m, mod)
        tmp = 1
        for i in range(n):
            ans -= tmp * fact.fac_inv(i) * k_pow % mod
            ans %= mod
            tmp *= m - i
            tmp %= mod
            k_pow *= k_inv
            k_pow %= mod
        print(ans)