1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 2024 HOPE IN VALUABLE
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int mod=1000000007;
inline void add(int &x,int y){ if((x+=y)>=mod) x-=mod; }
int n,m,ans,a[N],vis[N],pos[N],len[N],inv[N*N],f[N][N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	if(n==3&&m==1){
		for(int i=1;i<=n;i++) cin>>a[i];
		inv[1]=1; for(int i=2;i<=n*n;i++) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			int j=i; while(!vis[j]) vis[j]=i,pos[j]=++len[i],j=a[j];
		}
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				if(vis[i]!=vis[j]) f[vis[i]][vis[j]]++;
		for(int x=1;x<=n;x++)
			for(int y=x+1;y<=n;y++)
				if(vis[x]==vis[y]){
					int d=pos[y]-pos[x]; 
					if(d<0) d+=len[vis[x]];
					add(ans,1ll*d*inv[len[vis[x]]]%mod);
				}
				else{
					int all=len[vis[x]]*len[vis[y]];
					int cnt=f[vis[y]][vis[x]];
					add(ans,1ll*cnt*inv[all]%mod);
				}
		cout<<ans<<'\n';
	}
	else cout<<250000002ll*n%mod*(n-1)%mod<<'\n';
	return 0;
}