Luogu AC，Acwing WA 了第二个数据，全输出 $1$ 。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int mod=1e9+9,N=1e5+10;

int frac[N],inv[N],f[N],to[N],vis[N],cnt;

void dfs(int u)
{
	vis[u]=true; cnt++;
	if(vis[to[u]]) return ;
	return dfs(to[u]);
}

inline int qpow(int a,int b)
{
	int res=1;
	if(b <= 0) return 1;
	a%=mod;
	while(b)
	{
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod; b>>=1;
	}
	return res;
}

int main()
{
// 	freopen("work.in","r",stdin); freopen("work.out","w",stdout);
	int t,n,p,ans,tot;
	frac[0]=inv[0]=1;
	for(int i=1;i<=1e5;i++)
	{
		frac[i]=(1ll*i*frac[i-1])%mod;
		inv[i]=qpow(frac[i],mod-2);
		f[i]=qpow(i,i-2);	
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		tot=0; ans=1; 
		for(int i=1;i<=n;i++) {vis[i]=false; scanf("%d",&p); to[i]=p;}
		for(int i=1;i<=n;i++)
			if(!vis[i])
			{
				cnt=0; dfs(i); tot++;
				ans=1ll*ans*f[cnt]%mod*inv[cnt-1]%mod;
			}
		printf("%lld\n",1ll*ans*frac[n-tot]%mod);
	}
// 	fclose(stdin); fclose(stdout);
	return 0;
}