#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 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*10+c-'0',c=getchar();return x*f;} const int MAXN=110,MAXM=1010,inf=1000000000000000000,Mod=1000000007; 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 gcd(int x,int y){return !x||!y?x|y:gcd(y%x,x);} int lcm(int x,int y){return !x||!y?x|y:x*y/gcd(x,y);} int n,m,k,tot,ans,a[MAXN],p[MAXN],vis[MAXN],cnt,jc[MAXM],ny[MAXM]; pii tp[MAXN]; int t[MAXN],f[MAXN][MAXM],g[MAXN][MAXM],dy[MAXM]; map<int,int>mp; void dfs(int now,int sum){ if(now==tot+1){ int tmp=0; for(int i=1;i<=k;i++)if(sum%p[i]==0)tmp=lcm(tmp,p[i]); if(tmp!=sum)return; dy[++cnt]=sum; mp[sum]=cnt; return; } int tmp=1; for(int i=0;i<=tp[now].sc;i++){ dfs(now+1,sum*tmp); tmp*=tp[now].fr; } } int C(int x,int y){return jc[x]*ny[x-y]%Mod*ny[y]%Mod;} void slv(){ n=read(),m=read(); for(int i=1;i<=m;i++)a[i]=read(); for(int i=1;i<=m;i++)if(!vis[i]){ int now=i; ++k; while(!vis[now])vis[now]=1,p[k]++,now=a[now]; } for(int i=1;i<=k;i++){ int tmp=p[i]; for(int j=2;j*j<=tmp;j++)if(tmp%j==0){ int ct=0; while(tmp%j==0)ct++,tmp/=j; t[j]=max(ct,t[j]); } if(tmp!=1)t[tmp]=max(1ll,t[tmp]); } for(int i=2;i<=100;i++)if(t[i])tp[++tot]=mk(i,t[i]); dfs(1,1); memset(f,0,sizeof(f)); f[0][0]=1; for(int i=1;i<=k;i++){ memcpy(g,f,sizeof(f)); for(int r=0;r<=cnt;r++){ int rp=mp[lcm(dy[r],p[i])]; for(int j=1;j<=n;j++){ for(int o=0;o<j;o++){ f[rp][j]+=g[r][o]*Pow(p[i],j-o)%Mod*C(n-o,j-o)%Mod; f[rp][j]%=Mod; } } } } for(int i=1;i<=cnt;i++){ ans+=f[i][n]*(dy[i]%Mod)%Mod; ans%=Mod; } printf("%lld",ans*Pow(Pow(m,n),Mod-2)%Mod); } signed main(){ jc[0]=ny[0]=1;for(int i=1;i<=MAXM-5;i++)jc[i]=jc[i-1]*i%Mod,ny[i]=Pow(jc[i],Mod-2); slv(); return 0; }