#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define LL long longconst int MAXN = 200005;const int MOD = 1e9 + 7;int nt[MAXN];int two[MAXN];int part[MAXN];int visit[MAXN];int acyc[MAXN], acyn[MAXN];int n, cyc, cyn;void dfs2(int u){	visit[u] = 3;	acyc[cyc] ++;	if(visit[nt[u]] == 3) return ;	dfs2(nt[u]);}void dfs(int u){		visit[u] = 2;	if(visit[nt[u]] == 0){		dfs(nt[u]);	}	else if(visit[nt[u]] == 1){		cyn = part[nt[u]];	//	visit[nt[u]] = 1;	}	else{		cyc ++;		cyn = cyc;		dfs2(nt[u]);	}	visit[u] = 1;	part[u] = cyn;	acyn[cyn]++;}int main(){			two[0] = 1;	for(int i =1 ; i < MAXN; i++)		two[i] = (two[i - 1] * 2) % MOD;			scanf("%d", &n);	memset(visit, 0, sizeof(visit));	memset(part, -1, sizeof(part));	for(int i = 1; i <= n; i++)		scanf("%d", &nt[i]);		cyc = cyn = 0;		for(int i = 1; i <= n; i++){		if(visit[i] == 0){			cyn = 0;			dfs(i);		}	}		int ans = 1;	/*	for(int i = 1; i <= n; i++)		printf("%d  ", part[i]);	puts("");		for(int i = 0; i <= cyc; i++){		printf("%d %d \n", acyc[i], acyn[i]);	}*/		for(int i = 0; i <= cyc; i++){		if(i == 0 && acyn[i] > 0){			ans = ((LL)ans * two[acyn[i] - 1])%MOD;		}		if(i > 0){			ans = (LL)ans * (two[acyn[i]] - (LL)2 * two[acyn[i] - acyc[i]]) % MOD;		}	}	if(ans < 0) ans = ((LL)ans + MOD) % MOD;		printf("%d\n", ans);		return 0;}

/*****************设 2^n = m ,分母为 m ^k ,算的分子为 m * (m - 1) *.... * (m - k + 1)只要两个互质，最后用1减就是了，至于化简的过程，就是对分子提取因子2.边界 太多，搞了一晚……不划算***********/#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>using namespace std;#define LL long longconst int MOD =1000003;int mod[MOD + 5];bool vis[MOD + 5];LL tail[100];int quick(int m, LL k){	int ret = 1;	int pow = m;	while(k){		if(k&1)		ret = (LL)ret * pow % MOD;		k >>= 1;		pow = (LL)pow * pow % MOD;	}	return ret;}int cal(LL n, int index){		int m = quick(2, n);	int ret = 1;	int counts = 0;		memset(vis, false, sizeof(vis));		for(LL i = 1; i <= tail[index]; i += 2){		if(vis[(((LL)m - i)%MOD + MOD)%MOD]){			break;		}		mod[counts++] = (((LL)m - i)%MOD + MOD) %MOD;		vis[mod[counts - 1]] = true;	}	//	cout << counts << endl;		LL mc = tail[index] / 2  + 1;	LL cc = mc / counts;		mc = mc % counts;		for(int i = 0; i < counts; i++)		ret = ((LL)ret * mod[i]) % MOD;		ret = quick(ret, cc);	for(int i = 0; i < mc; i++){		ret = ((LL)ret * mod[i]) %MOD;	}	//	cout <<"endl" << endl;		return ret;			}int main(){		LL n, k, tmp;	int counts = 0;	cin >> n >> k;		double tt = log(k) / log(2) - n;		if(n < 64){		if( tt > 1e-8){			cout << 1 << " " << 1 << endl;			return 0;		}		else if(tt < 1e-8){						LL ans = 1;						for(LL i = 1; i <= n; i++)				ans = ans * 2;						if(ans > 0 && ans < k){				cout << 1<< " "<< 1 << endl;				return 0;			}								}	}		tmp = k - 1;		LL upc = 0;		while(tmp){				if(tmp % 2 == 0){						upc += tmp / 2;						tail[counts++] = tmp - 1;			tmp = tmp / 2;		}		else {			upc += tmp / 2;			tail[counts++] = tmp;			tmp = (tmp - 1) / 2;		}			}	//	cout << upc << endl << endl;		LL k_1 = k - 1 - upc;		int down = quick(2, n - 1);	down = quick(down, k - 1);	down = (LL)down * quick(2, k_1) % MOD;			int up = 1;	//	cout << down <<endl;	//	cout << "YES" << counts <<endl;		for(int i = 0; i < counts; i++){		up = ((LL)up * cal(n - i, i))%MOD;	}		up = ((down - up) % MOD + MOD) %MOD;		cout << up  <<" "<< down << endl;}