#include #include #include #include #include using namespace std; int N, A[100009], B[100009], col1[100009], cnt1[100009], S1[100009], col2[100009], cnt2[100009], S2[100009], cnts1, cnts2; vector>G; map, vector>M; map, long long>MM; long long extgcd(long long a, long long b, long long &x, long long &y) { long long d = a; if (b != 0) { d = extgcd(b, a%b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } long long Div(long long a, long long b, long long mod) { long long x, y; extgcd(b, mod, x, y); return ((x % mod + mod) % mod)*a%mod; } void dfs1(int pos, int v) { col1[pos] = cnts1; cnt1[pos] = v; S1[cnts1]++; if (col1[A[pos]] == 0) { dfs1(A[pos], v + 1); } } void dfs2(int pos, int v) { col2[pos] = cnts2; cnt2[pos] = v; S2[cnts2]++; if (col2[B[pos]] == 0) { dfs2(B[pos], v + 1); } } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } int main() { cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; for (int i = 1; i <= N; i++) cin >> B[i]; for (int i = 1; i <= N; i++) { if (col1[i] == 0) { cnts1++; dfs1(i, 0); } } for (int i = 1; i <= N; i++) { if (col2[i] == 0) { cnts2++; dfs2(i, 0); } } for (int i = 1; i <= N; i++) { long long F1 = S1[col1[i]], F2 = S2[col2[i]], K = F1*F2 / gcd(F1, F2), KK = gcd(F1, F2); long long T = 1LL * cnt1[i] * (K / F1) + 1LL * cnt2[i] * (K / F2); if (T >= K) T -= K; long long U = (cnt1[i] - cnt2[i] + K) % KK; long long TT = Div(T, ((K / F1) + (K / F2)) % K, K); G.push_back(make_tuple(col1[i], col2[i], U)); M[make_tuple(col1[i], col2[i], U)].push_back(TT); MM[make_tuple(col1[i], col2[i], U)] = K; } sort(G.begin(), G.end()); G.erase(unique(G.begin(), G.end()), G.end()); long long ans = 0; for (int i = 0; i < G.size(); i++) { vector Z = M[G[i]]; sort(Z.begin(), Z.end()); long long B = Z[0]; for (int j = 0; j < Z.size(); j++) Z[j] -= B; for (int j = 0; j < Z.size(); j++) { long long GG = Z[(j + 1) % Z.size()] - Z[j]; if (j == Z.size() - 1) GG += MM[G[i]]; ans += GG * (GG - 1) / 2; ans %= 1000000007; } } cout << ans << endl; return 0; }