#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define popcnt __builtin_popcount #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,f[(1<<15)+10],g[(1<<15)+10]; pii tp[MAXN]; map<int,int>mp; 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]; } sort(p+1,p+k+1); for(int i=1;i<=k;i++){if(p[i]!=p[i-1])tp[tot++].fr=p[i];tp[tot-1].sc++;} // for(int i=0;i<tot;i++)cout<<tp[i].fr<<" "<<tp[i].sc<<endl; for(int i=1;i<1<<tot;i++){ f[i]=g[i]=0; int lc=0,sum=0; for(int j=0;j<tot;j++)if(i&(1<<j))sum+=tp[j].fr*tp[j].sc%Mod,sum%=Mod,lc=lcm(lc,tp[j].fr); f[i]=Pow(sum,n); for(int j=i;j;j=(j-1)&i){ g[i]+=f[j]*((popcnt(i)-popcnt(j))&1?-1:1); g[i]%=Mod; } ans+=g[i]*lc%Mod; ans%=Mod; // cout<<i<<" "<<f[i]<<" "<<g[i]<<" "<<lc<<endl; } printf("%lld",(ans+Mod)%Mod*Pow(Pow(m,n),Mod-2)%Mod); } signed main(){ slv(); return 0; }