CF711D-Directed Roads(组合数学 dfs找环)

// Problem: D. Directed Roads
// Contest: Codeforces Round #369 (Div. 2)
// URL: https://codeforces.com/contest/711/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn=2e5+100;
const ll mod=1e9+7;
int n,a[maxn],siz[maxn],vis[maxn];
vector<int>g[maxn];
vector<int>w;
void dfs(int u,int sum){
  vis[u]=1;
  siz[u]=sum;
  for(auto t:g[u]){
    if(!vis[t]) dfs(t,sum+1);
    else if(vis[t]==1){
      w.push_back(siz[u]-siz[t]+1);
    }
  }
  vis[u]=2;
}
int main(){
  n=read;
  rep(i,1,n){
    g[i].push_back(read);
  } 
  rep(i,1,n){
    if(!siz[i]) dfs(i,1);
  }
  ll ans=1,tot=0;
  for(auto t:w){
    tot+=t;
    ans=ans*(ksm(2,t,mod)-2+mod)%mod;
  }
  ans=ans*ksm(2,n-tot,mod)%mod;
  cout<<ans<<endl;
    return 0;
}