#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- struct UnionFind {vector par; // uf(x,y)->y UnionFind(int NV) { par.clear(); rep(i, 0, NV) par.push_back(i); } void reset() { rep(i, 0, par.size()) par[i] = i; } int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); } void operator()(int x, int y) {x = operator[](x); y = operator[](y);if (x != y) par[x] = y;}}; template struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) { } ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } bool operator==(ModInt that) const { return x == that.x; } bool operator!=(ModInt that) const { return x != that.x; } ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; template ostream& operator<<(ostream& st, const ModInt a) { st << a.get(); return st; }; template ModInt operator^(ModInt a, unsigned long long k) { ModInt r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } typedef ModInt<1000000007> mint; typedef long long ll; ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; } // なるべく上限付きLCM使おう ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, A[101010], B[101010]; //--------------------------------------------------------------------------------------------------- int vis[1010][1010]; int f(int a, int b) { if (vis[a][b]) return -101010; vis[a][b] = 1; if (a == b) return 0; return f(A[a], B[b]) + 1; } //--------------------------------------------------------------------------------------------------- set E[101010]; int CA[101010], CB[101010]; map, int> CC; void _main() { cin >> N; rep(i, 0, N) cin >> A[i], A[i]--; rep(i, 0, N) cin >> B[i], B[i]--; UnionFind AU(N), BU(N); rep(i, 0, N) CA[i] = CB[i] = 1; rep(i, 0, N) { if (AU[i] != AU[A[i]]) { int c = CA[AU[i]] + CA[AU[A[i]]]; AU(i, A[i]); CA[AU[i]] = c; } } rep(i, 0, N) { if (BU[i] != BU[B[i]]) { int c = CB[BU[i]] + CB[BU[B[i]]]; BU(i, B[i]); CB[BU[i]] = c; } } mint ans = 0; rep(i, 0, N) { E[AU[i]].insert(BU[i]); CC[{AU[i], BU[i]}]++; } rep(i, 0, N) if (AU[i] == i) { fore(b, E[i]) if(CA[i] != CB[b]){ ll lc = lcm(CA[i], CB[b]); int c = CC[{AU[i], BU[i]}]; if (max(CA[i], CB[b]) % min(CA[i], CB[b]) == 0 and 2 <= min(CA[i], CB[b])) c++; if (min(CA[i], CB[b]) == 1) c = 1; mint d = (mint(lc % 1000000007 - c + 1)) * (mint(lc % 1000000007) - c) / 2; ans += d; //printf("[%d(%d) %d(%d)] -> %d\n", i + 1, CA[i], b + 1, CB[b], d.get()); } } cout << ans << endl; return; printf("CHECK!\n"); int ans2 = 0; rep(i, 0, N) if(AU[i] == i) fore(b, E[i]) if(CA[i] != CB[b]) { vector va, vb; rep(j, 0, N) if (AU[j] == AU[i]) va.push_back(j); rep(j, 0, N) if (BU[j] == BU[b]) vb.push_back(j); int sm = 0; vector v; fore(aa, va) fore(bb, vb) { rep(j, 0, N) rep(k, 0, N) vis[j][k] = 0; int x = f(aa, bb); if (x < 0) continue; sm += x; v.push_back(x); } sort(v.begin(), v.end()); printf("[%d(%d) %d(%d)] -> %d (", i + 1, CA[i], b + 1, CB[b], sm); fore(j, v) printf("%d ", j); printf(")\n"); ans2 += sm; } printf("%d\n", ans2); }