#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=500010,N=410,base=2333,Mod=1e9+7; inline void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;if(x<0)x+=Mod;} int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} int n,m,k,ans,a[MAXN],p[MAXN]; struct SLV1{ int f[2][N],g[2][N]; void slv1(){ ans=(n-m+1)*Pow(k,n-m)%Mod; f[0][0]=1; for(int j=k;j>=0;j--)f[0][j]+=f[0][j+1]; for(int i=1;i<=n;i++){ for(int j=k-1;j>=0;j--){ if(j)g[0][j]=((f[0][j-1]-f[0][j]+Mod)*(k-j+1)+f[0][j])%Mod, g[1][j]=((f[1][j-1]-f[1][j]+Mod)*(k-j+1)+f[1][j])%Mod; else g[0][j]=0,g[1][j]=0; if(j>=m)add(g[1][j],g[0][j]); } for(int j=k;j>=0;j--){ f[0][j]=g[0][j],add(f[0][j],f[0][j+1]); f[1][j]=g[1][j],add(f[1][j],f[1][j+1]); } } int tmp=f[1][0],tmp2=1; for(int i=k;i>k-m;i--)tmp2=tmp2*i%Mod; tmp=tmp*Pow(tmp2,Mod-2)%Mod; add(ans,Mod-tmp); printf("%lld",ans); } }S1; struct SLV2{ int f[N],g[N],c[MAXN],d[MAXN]; void slv2(){ int L=0,R=0; for(int i=1;i<=m;i++)if(p[a[i]]){L=i-1;break;}else p[a[i]]=1; for(int i=1;i<=L;i++)p[a[i]]=0; for(int i=m;i>=1;i--)if(p[a[i]]){R=m-i;break;}else p[a[i]]=1; for(int i=m;i>m-R;i--)p[a[i]]=0; f[L]=1;c[0]=1; for(int j=k;j>=0;j--)f[j]+=f[j+1]; for(int i=1;i<=n-m;i++){ for(int j=k-1;j>=0;j--){ if(j)g[j]=((f[j-1]-f[j]+Mod)*(k-j+1)%Mod+f[j]+g[j+1])%Mod; else g[j]=g[j+1]; } add(c[i],g[0]); for(int j=0;j<k;j++)swap(f[j],g[j]),g[j]=0; } for(int i=0;i<=k;i++)f[i]=0; f[R]=1;d[0]=1; for(int j=k;j>=0;j--)f[j]+=f[j+1]; for(int i=1;i<=n-m;i++){ for(int j=k-1;j>=0;j--){ if(j)g[j]=((f[j-1]-f[j]+Mod)*(k-j+1)%Mod+f[j]+g[j+1])%Mod; else g[j]=g[j+1]; } add(d[i],g[0]); for(int j=0;j<k;j++)swap(f[j],g[j]),g[j]=0; } ans=(n-m+1)*Pow(k,n-m)%Mod; for(int i=0;i<=n-m;i++)add(ans,Mod-c[i]*d[n-m-i]%Mod); printf("%lld",ans); } }S2; void slv(){ n=read(),m=read(),k=read(); for(int i=1;i<=m;i++)a[i]=read(); bool fl=0,fl2=0; int lst=0; for(int i=1;i<=m;i++){ lst=min(lst+1,i-p[a[i]]); fl|=p[a[i]],p[a[i]]=i; if(lst==k)fl2=1; } if(fl2){ printf("%lld",(n-m+1)*Pow(k,n-m)%Mod); return; } for(int i=1;i<=k;i++)p[i]=0; if(!fl)S1.slv1(); else S2.slv2(); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s"<<endl; return 0; }