I too did not get it

Instead of counting the number of arrays of length $$$m$$$ which have $$$a$$$ as a sub-sequence.
We will count the number of arrays which DO NOT have $$$a$$$ as their sub-sequence (read the last paragraph before the "Note" to understand why this cannot be done to find the answer more directly) and subtract that from the total number of arrays (of length $$$m$$$).
There are a total of $$$k^m$$$ arrays of length $$$m$$$ (since each element can be anything from $$$[1,k]$$$).

To find the number of sequences which don't have $$$a$$$ as their subsequence.
We can go ahead and count the number of arrays $$$b$$$ which have prefix of $$$a$$$ till length $$$i$$$ (and sum up for all $$$i$$$ in $$$0$$$ to $$$n-1$$$).
To do this we shall choose $$$i$$$ spots out of $$$m$$$ for placing first $$$i$$$ elements of $$$a$$$.
To help with understanding, say the $$$i$$$ spots are $$$p_1$$$, $$$p_2$$$$$$...$$$$$$p_i$$$ (in increasing order).
Till I reach $$$p_1$$$, I will not place any element equal to $$$a_1$$$, leaving only $$$k-1$$$ choices for each spot. Once on $$$p_1$$$, I will assign it the value $$$a_1$$$ in $$$1$$$ way. then proceed to not assign $$$a_2$$$ to any element till I reach $$$p_2$$$ (in $$$k-1$$$ ways per spot) and so on.
The number of ways to choose are $$${m}\choose{i}$$$ and the ways to assign values for all such selections ($$$m-i$$$ in total) are $$$(k-1)^{m-i}$$$
we are to find:-

$$$k^m - \sum_{i=0}^{n-1}\binom{m}{i}.(k-1)^{m-i}$$$

One can use inverse modulo ideas and the fact that $$$\binom{n}{r} = \frac{n-r+1}{r}.\binom{n}{r-1}$$$

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long mod = (long long) 1e9 + 7;
long long po(long long x, long long y)
{
	long long ans = 1;
	x %= mod;
	while(y>0)
	{
		if(y&1)
		{
			ans = (ans*x) % mod;
		}
		y /= 2;
		x = (x * x)% mod; 
	}
	return ans;
}
int solve()
{
	long long n, m, k, bin=1;
	cin>>n>>m>>k;
	long long ans = po(k, m);
	long long arr[n];
	for(int i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	for(int i=0; i<n; i++)
	{
		long long sub = (bin*po(k-1, m-i))%mod;
		ans -= sub; ans = (ans+mod)%mod;
		bin *= (m-i); bin %= mod;
		bin *= po(i+1, mod-2); bin %= mod;		
	}	
	cout<<ans<<endl;
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{	
		solve();
	}
	return 0;		
}

Why not directly do it? (the note before the "Note")
If you tried to find the arrays such that $$$a$$$ is a subsequence directly. You might want to choose $$$n$$$ spots out of $$$m$$$. but say the largest chosen element is $$$p_n$$$. now for all indexes in $$$b$$$ greater than $$$p_n$$$ (the array we are constructing) you can place any number out of those $$$k$$$. so the power of $$$k$$$ is heavily dependent on $$$p_n$$$ (there will be some $$$(k-1)$$$ terms too) which is not easy to deal with (we are choosing all sorts of elements, so, keeping track of the highest element and computing based on it isn't easy!)

Note — I am not familiar with writing using LaTeX or anything, neither do I know how to align stuff here.
Inconvenience is regretted.