#include <bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long #define ull unsigned long long #define uint unsigned int #define bi __int128_t #define lb(x) ((x)&(-(x))) #define gp(i,j) (((i)>>(j-1))&1) #define ppc __builtin_popcount using namespace std; const int N=26000,M=410,mod=1e9+7; const ll inf=1e18+10; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} void Sub(int &a,int b){a-=b;if(a<0) a+=mod;} void Mul(int &a,int b){a=1ll*a*b%mod;} int qp(int a,int b){ int x=1; while(b){ if(b&1) Mul(x,a); Mul(a,a);b>>=1; }return x; } int f[N][M],g[N][M]; int n,m,k; int a[N]; map<int,int> mp; bool vis[M]; bool chk(int l,int r){ for(int i=1;i<=k;i++) vis[i]=0; for(int i=l;i<=r;i++) vis[a[i]]=1; for(int i=1;i<=k;i++) if(!vis[i]) return 0; return 1; } bool chk1(){ for(int i=k;i<=m;i++){ if(chk(i-k+1,i)) return 1; }return 0; } bool chk2(){ for(int i=1;i<=k;i++){ if(mp[i]>1) return 1; }return 0; } void slv(){ cin>>n>>m>>k; for(int i=1;i<=m;i++) cin>>a[i]; for(int i=1;i<=m;i++) mp[a[i]]++; int ans=1ll*(n-m+1)*qp(k,n-m)%mod; if(k>n){ cout<<0<<endl; }else if(chk1()){ cout<<ans<<endl; }else if(chk2()){ int v=0; map<int,int> ct; for(int i=m;i>=1;i--){ if(ct[a[i]]) break; else ct[a[i]]=1,v++; }f[0][v]=1; ct.clear();v=0; for(int i=1;i<=m;i++){ if(ct[a[i]]) break; else ct[a[i]]=1,v++; }g[0][v]=1; for(int i=1;i<=n+1;i++){ for(int j=k-1;j>=1;j--){ Add(f[i][j+1],1ll*f[i-1][j]*(k-j)%mod); Add(g[i][j+1],1ll*g[i-1][j]*(k-j)%mod); if(j!=k-1){ Add(f[i-1][j],f[i-1][j+1]); Add(g[i-1][j],g[i-1][j+1]); } Add(f[i][j],f[i-1][j]); Add(g[i][j],g[i-1][j]); } } for(int i=1;i<=n-m+1;i++){ int A=i-1,B=n-(i-1)-m; //cout<<A<<' '<<B<<' '<<f[A][1]<<' '<<g[B][1]<<endl; if(k!=1) Sub(ans,1ll*f[A][1]*g[B][1]%mod); }cout<<ans<<endl; }else{ f[1][1]=k; g[1][1]=1ll*k*(m<=1); for(int i=2;i<=n+1;i++){ for(int j=k-1;j>=1;j--){ Add(f[i][j+1],1ll*f[i-1][j]*(k-j)%mod); Add(g[i][j+1],1ll*g[i-1][j]*(k-j)%mod); if(j!=k-1){ Add(f[i-1][j],f[i-1][j+1]); Add(g[i-1][j],g[i-1][j+1]); } Add(f[i][j],f[i-1][j]); Add(g[i][j],g[i-1][j]); } for(int j=k-1;j>=1;j--){ if(j>=m) Add(g[i][j],f[i][j]); //cout<<i<<' '<<j<<' '<<f[i][j]<<' '<<g[i][j]<<endl; } } int val=g[n][1]; for(int i=k;i>=k-m+1;i--) Mul(val,qp(i,mod-2)); Sub(ans,val); cout<<ans<<endl; } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1;//cin>>t; while(t--) slv(); cout.flush(); return 0; }