#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=(1<<16)+7; const int mod=1e9+7; inline int gcd(int a,int b){return !b?a:gcd(b,a%b);} inline int lcm(int a,int b){return a/gcd(a,b)*b;} inline int qpow(int a,int b){ int ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int n,m; int b[maxn]; int c[maxn]; inline int slv(int x,int t){ if(x==t)return 0; return slv(b[x],t)+1; } int CNT[maxn]; vector<int> Lis; int N; int Val[maxn]; int a[maxn]; signed main(){ // freopen("baka.in","r",stdin); // freopen("baka.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++)cin>>b[i]; for(int i=1;i<=m;i++)c[i]=slv(b[i],i)+1,CNT[c[i]]++; for(int i=1;i<=m;i++)if(CNT[i])Lis.push_back(i); N=Lis.size(); for(int S=1;S<(1<<N);S++){ int L=1; for(int j=0;j<N;j++)if(S&(1<<j))L=lcm(L,Lis[j]); Val[S]=L; } for(int S=0;S<(1<<N);S++){ for(int j=0;j<N;j++){ if(S&(1<<j))a[S]+=CNT[Lis[j]]; } } // cout<<"PRE"<<endl; for(int S=0;S<(1<<N);S++)a[S]=qpow(a[S],n); for(int m=1,L=2;L<=(1<<N);m=L,L<<=1){ for(int l=0;l<(1<<N);l+=L){ for(int j=0;j<m;j++)a[l+j+m]=(a[l+j+m]-a[l+j]+mod)%mod; } } // cout<<"FWT"<<endl; int ans=0; for(int S=0;S<(1<<N);S++)(ans+=(Val[S]*a[S]%mod))%=mod; (ans*=qpow(m,mod-1-n))%=mod; cout<<ans<<endl; return 0; }