Language: C++

#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
const int mod = 1e9+7,N = 25100;
int n,k,m,a[N];
ll ans;
void upd(int&a,ll b){a=(a+b)%mod;}
ll fp(ll a,ll k){
	ll ans=1;
	for(;k;k>>=1,a=a*a%mod)
		if(k&1) ans=a*ans%mod;
	return ans;
}
int main(){
	read(n);read(k);read(m);
	int flag=0,flag2=m>k;
	for(int i=1;i<=m;i++){
		read(a[i]);
		if(i>=k){
			int h[k]={},now=1;
			for(int j=i-k+1;j<=i;j++)
				if(++h[a[j]]==2) now=0;
			flag|=now;
		}
		if(!flag2)
			for(int j=1;j<i;j++)
				flag2|=a[i]==a[j];
	}
	if(flag&&m>=k){
		ll ans=fp(k,n-m)*(n-m+1)%mod;
		cout<<(ans+mod)%mod<<'\n';
		return 0;
	}
	if(flag2){
		int g1[N][410]={},g2[N][410]={};
		for(int i=1;i<=k;i++){
			int flg=0;
			for(int j=1;j<i;j++)
				if(a[i]==a[j]){flg=1;break;}
			if(flg){g1[0][i-1]=1;break;}
		}
		for(int i=1;i<=k;i++){
			int flg=0;
			for(int j=1;j<i;j++)
				if(a[m-i+1]==a[m-j+1]){flg=1;break;}
			if(flg){g2[0][i-1]=1;break;}
		}
		for(int i=1;i<=n;i++){
			for(int j=k-1;j;j--){
				upd(g1[i][j],g1[i-1][j]+g1[i][j+1]);
				upd(g2[i][j],g2[i-1][j]+g2[i][j+1]);
			}
			for(int j=1;j<k;j++){
				upd(g1[i][j],1ll*g1[i-1][j-1]*(k-j+1));
				upd(g2[i][j],1ll*g2[i-1][j-1]*(k-j+1));
			}
		}
		for(int i=0;i<=n;i++){
			for(int j=1;j<k;j++)
				upd(g1[i][0],g1[i][j]),
				upd(g2[i][0],g2[i][j]);
		}
		for(int i=1;i<=n-m+1;i++){
			ans=(ans+1ll*g1[i-1][0]*g2[n-i-m+1][0])%mod;
		}
	}
	else{
		int g[N][410][2]={};
		g[0][0][0]=1;
		for(int i=1;i<=n;i++){
			for(int j=k-1;j;j--){
				upd(g[i][j][0],g[i-1][j][0]+g[i][j+1][0]);
				upd(g[i][j][1],g[i-1][j][1]+g[i][j+1][1]);
			}
			for(int j=1;j<k;j++){
				upd(g[i][j][0],1ll*g[i-1][j-1][0]*(k-j+1));
				upd(g[i][j][1],1ll*g[i-1][j-1][1]*(k-j+1));
			}
			for(int j=m;j<k;j++)
				upd(g[i][j][1],g[i][j][0]);
		}
		for(int i=1;i<k;i++) ans=(ans+g[n][i][1])%mod;
		ll cef=1;
		for(int i=k-m+1;i<=k;i++) cef=cef*i%mod;
		ans=ans*fp(cef,mod-2)%mod;
	}
	ans=((n-m+1)*fp(k,n-m)-ans)%mod;
	cout<<(ans+mod)%mod<<'\n';
	return 0;
}


Compiler output:
a.cc: In function 'void read(tn&)':
a.cc:5:15: error: there are no arguments to 'isdigit' that depend on a template parameter, so a declaration of 'isdigit' must be available [-fpermissive]
    5 |         for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
      |               ^~~~~~~
a.cc:5:15: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc:5:28: error: there are no arguments to 'getchar' that depend on a template parameter, so a declaration of 'getchar' must be available [-fpermissive]
    5 |         for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
      |                            ^~~~~~~
a.cc:6:14: error: there are no arguments to 'isdigit' that depend on a template parameter, so a declaration of 'isdigit' must be available [-fpermissive]
    6 |         for(;isdigit(c);c=getchar()) x=x*10+c-'0';
      |              ^~~~~~~
a.cc:6:27: error: there are no arguments to 'getchar' that depend on a template parameter, so a declaration of 'getchar' must be available [-fpermissive]
    6 |         for(;isdigit(c);c=getchar()) x=x*10+c-'0';
      |                           ^~~~~~~
a.cc: In function 'int main()':
a.cc:36:17: error: 'cout' was not declared in this scope
   36 |                 cout<<(ans+mod)%mod<<'\n';
      |                 ^~~~
a.cc:1:1: note: 'std::cout' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
  +++ |+#include <iostream>
    1 | #define ll long long
a.cc:93:9: error: 'cout' was not declared in this scope
   93 |         cout<<(ans+mod)%mod<<'\n';
      |         ^~~~
a.cc:93:9: note: 'std::cout' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
a.cc: In instantiation of 'void read(tn&) [with tn = int]':
a.cc:20:6:   required from here
   20 |         read(n);read(k);read(m);
      |         ~~~~^~~
a.cc:5:22: error: 'isdigit' was not declared in this scope
    5 |         for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
      |               ~~~~~~~^~~
a.cc:5:35: error: 'getchar' was not declared in this scope
    5 |         for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
      |                            ~~~~~~~^~
a.cc:1:1: note: 'getchar' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
  +++ |+#include <cstdio>
    1 | #define ll long long
a.cc:6:21: error: 'isdigit' was not declared in this scope
    6 |         for(;isdigit(c);c=getchar()) x=x*10+c-'0';
      |              ~~~~~~~^~~
a.cc:6:34: error: 'getchar' was not declared in this scope
    6 |         for(;isdigit(c);c=getchar()) x=x*10+c-'0';
      |                           ~~~~~~~^~
a.cc:6:34: note: 'getchar' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'