#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=3e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k,m,a[maxn]; inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } inline int add(int a,int b){if((a+=b)>=mod)a-=mod;return a;} int f[1005][105]; int s0[maxn],s1[maxn],s2[maxn],s3[maxn]; int len1,len2; int solve1(int p){ int S0=s0[p-1],S1=s1[p-1]; int S2=s2[n-(p+m-1)],S3=s3[n-(p+m-1)]; return add(S0*1ll*add(S2,S3)%mod,S1*1ll*S2%mod); } int s[405]; int dp[2][405][2]; int mp[maxn]; int jc[1005],jc_inv[1005]; int A(int n,int m){return jc[m]*1ll*jc_inv[m-n]%mod;} void slv(){ n=read(),m=read(),k=read(); if(n<k)return printf("0"),void(); up(i,1,m)a[i]=read(); int cnt=0; up(i,1,k-1)cnt+=!(mp[a[i]]++); up(i,1,m-k+1){ if(i>1){if(!(--mp[a[i-1]]))--cnt;} cnt+=!(mp[a[i+k-1]]++); if(cnt==k){ int res=(n-m+1)*1ll*qp(k,n-m)%mod; return printf("%d\n",res),void(); } } memset(mp,0,sizeof(mp)); bool ck=1; up(i,1,m){ ck&=!mp[a[i]]; if((!len1)&&(!ck))len1=i-1; mp[a[i]]=1; } ck=1;memset(mp,0,sizeof(mp)); down(i,m,1){ ck&=!mp[a[i]]; if((!len2)&&(!ck))len2=m-i; mp[a[i]]=1; } int res=0; if(!ck){ f[0][len1]=1; up(i,0,n){ int op=i&1; if(i){ memset(f[op],0,sizeof(f[op])); f[op][k]=f[!op][k]*1ll*k%mod; up(j,0,k-1){ f[op][j+1]=add(f[op][j+1],f[!op][j]*1ll*(k-j)%mod); //up(p,1,j)f[i][p]=add(f[i][p],f[i-1][j]); } } int sm=0; down(j,k-1,1)sm=add(sm,f[!op][j]),f[op][j]=add(f[op][j],sm); s0[i]=f[op][k];up(j,1,k-1)s1[i]=add(s1[i],f[op][j]); } memset(f,0,sizeof(f)); f[0][len2]=1; up(i,0,n){ int op=i&1; if(i){ memset(f[op],0,sizeof(f[op])); f[op][k]=f[!op][k]*1ll*k%mod; up(j,0,k-1){ f[op][j+1]=add(f[op][j+1],f[!op][j]*1ll*(k-j)%mod); //up(p,1,j)f[i][p]=add(f[i][p],f[i-1][j]); } } int sm=0; down(j,k-1,1)sm=add(sm,f[!op][j]),f[op][j]=add(f[op][j],sm); s2[i]=f[op][k];up(j,1,k-1)s3[i]=add(s3[i],f[op][j]); } up(i,1,n-m+1)res=add(res,solve1(i)); } else { jc[0]=jc_inv[0]=1;up(i,1,1000)jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qp(jc[i],mod-2); dp[1][1][0]=k; up(i,1,n){ int op=i&1; up(j,m,k-1)dp[op][j][1]=add(dp[op][j][1],dp[op][j][0]); memset(dp[!op],0,sizeof(dp[!op])); if(i==n)break; up(j,1,k-1)up(o,0,1)dp[!op][j+1][o]=add(dp[!op][j+1][o],dp[op][j][o]*1ll*(k-j)%mod); up(o,0,1){ int s=0; down(j,k-1,1)s=add(s,dp[op][j][o]),dp[!op][j][o]=add(dp[!op][j][o],s); } } //res=dp[n&1][k][1]; up(i,1,k-1)res=add(res,dp[n&1][i][1]); res=res*1ll*qp(A(m,k),mod-2)%mod; res=add(qp(k,n-m)*1ll*(n-m+1)%mod,mod-res); } cout<<res; } int main(){ //freopen("gch.in","r",stdin),freopen("gch.out","w",stdout); slv(); return 0; }