Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define MAXN 200010
- #define LL long long
- using namespace std;
- const LL P=1000000007;
- LL getPow(LL x,LL y){
- LL res=1;
- while(y){
- if(y&1) res=res*x%P;
- x=x*x%P;
- y>>=1;
- }
- return res;
- }
- struct edge{
- int to,next;
- edge(int _to=0,int _next=0):to(_to),next(_next){}
- }e[MAXN];
- int n;
- int g[MAXN],nume;
- int p[MAXN];
- bool visit0[MAXN],visit[MAXN];
- int b[MAXN],l[MAXN],sl[MAXN],numb;
- int cnt[MAXN];
- LL f[MAXN],fac[MAXN],invfac[MAXN];
- LL ans=1;
- void addEdge(int u,int v){
- e[nume]=edge(v,g[u]);
- g[u]=nume++;
- }
- int dfs(int x){
- visit[x]=1;
- int numch=0;
- int res=0;
- for(int i=g[x];~i;i=e[i].next)
- if(!visit[e[i].to]){
- numch++;
- res=dfs(e[i].to)+1;
- }
- if(numch>=2) ans=0;
- return res;
- }
- void gao(int x){
- numb=0;
- while(!visit[x]){
- visit[x]=1;
- b[++numb]=x;
- x=p[x];
- }
- int pos=0;
- for(int i=1;i<=numb;i++){
- l[i]=dfs(b[i]);
- if(l[i]) pos=i;
- }
- if(!pos){
- cnt[numb]++;
- return;
- }
- for(int i=1;i<=numb;i++){
- b[i+numb]=b[i];
- l[i+numb]=l[i];
- b[i]=b[i+pos-1];
- l[i]=l[i+pos-1];
- }
- for(int i=1;i<=numb;i++) sl[i]=sl[i-1]+l[i];
- LL res1=0,res2=0;
- if(sl[numb]-sl[numb-(l[1]-1)]==0){
- res1=1;
- for(int i=2;i<=numb;i++){
- if(!l[i]) continue;
- LL temp=0;
- if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
- if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
- res1=res1*temp%P;
- }
- }
- if(sl[numb]-sl[numb-l[1]]==0){
- res2=1;
- for(int i=2;i<=numb;i++){
- if(!l[i]) continue;
- LL temp=0;
- if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
- if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
- res2=res2*temp%P;
- }
- }
- ans=ans*(res1+res2)%P;
- }
- void init(){
- f[0]=1;
- for(int i=2;i<=n;i++) f[i]=f[i-2]*(i-1)%P;
- fac[0]=1;
- for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
- invfac[n]=getPow(fac[n],P-2);
- for(int i=n-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
- }
- LL getC(int x,int y){
- return fac[x]*invfac[y]%P*invfac[x-y]%P;
- }
- int main(){
- #ifdef DEBUG
- freopen("E.in","r",stdin);
- #endif
- memset(g,-1,sizeof g);
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d",p+i);
- addEdge(p[i],i);
- }
- for(int i=1;i<=n;i++)
- if(!visit[i]){
- int x=i;
- for(;!visit0[x];x=p[x]) visit0[x]=1;
- gao(x);
- }
- init();
- for(int i=1;i<=n;i++)
- if(cnt[i]){
- LL res=0;
- for(int j=0;j<=cnt[i];j+=2)
- if(i>=3 && (i&1)) res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2)%P*getPow(2,cnt[i]-j))%P;
- else res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2))%P;
- ans=ans*res%P%P;
- }
- printf("%lld\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement