ABC247F - Cards

import std;

void main () {
    int N = readln.chomp.to!int;
    auto P = readln.split.to!(int[]);
    P[] -= 1;
    auto Q = readln.split.to!(int[]);
    Q[] -= 1;

    solve(N, P, Q);
}

void solve (int N, int[] P, int[] Q) {
    // カードを3種類に分類する。
    // 1. 表と裏で同じ数が書いている
    // 2. 同じ数字の割り当てのカードが存在する
    // 3. 1, 2に当てはまらない

    // 1は必ずとる必要があるので、これを除く。
    // 2は少なくとも片方をとればよく、この枚数をxとして、任意の取り方が3^(x/2)倍になる。
    // 3をどう取るか？が本質

    const long MOD = 998244353;

    int[Tuple!(int, int)] count;
    foreach (i; 0..N) {
        count[tuple(min(P[i], Q[i]), max(P[i], Q[i]))]++;
    }

    int type1 = 0;
    foreach (i; 0..N) {
        if (tuple(i, i) in count) {
            type1++;
        }
    }

    int type2 = 0;
    foreach (key, val; count) {
        if (val == 2) {
            type2++;
        }
    }

    int[] type3;
    auto idx = new int[][](N, 0);
    foreach (i; 0..N) {
        idx[P[i]] ~= i;
        idx[Q[i]] ~= i;
    }

    auto UF = UnionFind(N);
    foreach (I; idx) {
        if (0 < I.length) {
            UF.unite(I[0], I[1]);
        }
    }

    foreach (i; 0..N) {
        if (UF.root(i) == i && 3 <= UF.GroupSize(i)) type3 ~= UF.GroupSize(i);
    }

    // 3のカードを(a, b)のように考えて、同じ数字を隣り合わせに配置してみると、円環になる。
    // この時、空白が高々サイズ1であることが有効なとり方の必要十分条件。
    // とるのととらないのをペア(ox)にしてやれば、何個とらないかで場合分けして組み合わせに帰着できる。

    // 具体的な帰着について考える。
    // oとoxの並べ替えと考えると、多項係数になる。
    // 頭がxになるようなものだけ無理なので、そのようなケースのみxoを使う数え上げもする。

    // WA -> 多分議論は合っていて、円環が複数できうるケースに対応できていないものと考えられる。

    alias m = PrimeModuloFactorial!MOD;
    m.build(N);

    long ans = 1;
    foreach (t3; type3) {
        long prod = 0;
        foreach (t; 0..N) {
            if (t3 < 2 * t) break;
            int r = t3 - 2 * t;

            if (t == 0) {
                prod++;
                continue;
            }

            { // ox数え上げ
                long add = m.factorial(t + r);
                add *= m.factorial_inv(t);
                add %= MOD;
                add *= m.factorial_inv(r);
                add %= MOD;

                prod += add;
                prod %= MOD;
            }
            { // xo数え上げ
                long add = m.factorial(t + r - 1);
                add *= m.factorial_inv(t - 1);
                add %= MOD;
                add *= m.factorial_inv(r);
                add %= MOD;

                prod += add;
                prod %= MOD;
            }
        }

        ans *= prod;
        ans %= MOD;
    }

    ans *= mod_pow(3, type2, MOD);
    ans %= MOD;

    writeln(ans);
}

// check mod_inv
static assert(__traits(compiles, mod_inv(998244353, 1_000_000_007)));

template PrimeModuloFactorial (ulong M)
if ((1 <= M && M < int.max)
    && ((x) {
        for (int i = 2; i < x; i++) {
            if (x < 1L*i*i) break;
            if (x % i == 0) return false;
        }
        return true;
    })(cast(int) M))
{
    import std.conv : to;
    import std.format : format;

    private:
        long[] fact, fact_inv;
        int N = 0;
        long MOD = M;

    public:
        void build (ulong N_) {
            N = N_.to!int;
            fact.length = fact_inv.length = N+1;

            fact[0] = 1;
            for (int i = 1; i <= N; i++) fact[i] = i * fact[i-1] % MOD;
            fact_inv[N] = mod_inv(fact[N], MOD);
            for (int i = N; 0 < i; i--) fact_inv[i-1] = i * fact_inv[i] % MOD;
        }

        long binom (ulong n_, ulong k_)
        in {
            assert((n_ < k_
                    || (n_ <= N && k_ <= N)),
                    format("Out of range of pre-calculation. MAX = %s, n = %s, k = %s.", N, n_, k_),
                    );
        }
        do {
            int n = n_.to!int;
            int k = k_.to!int;

            if (n < k) return 0;
            long res = fact[n] * fact_inv[k] % MOD;
            return res * fact_inv[n-k] % MOD;
        }

        long factorial (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_),
                    );
        }
        do {
            int x = x_.to!int;
            return fact[x];
        }

        long factorial_inv (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_)
                    );
        }
        do {
            int x = x_.to!int;
            return fact_inv[x];
        }
}

// check mod_pow
static assert(__traits(compiles, mod_pow(2, 10, 998244353)));

long mod_inv (const long x, const long MOD)
in {
    import std.format : format;
    assert(1 <= MOD, format("MOD must satisfy 1 <= MOD. Now MOD =  %s.", MOD));
    assert(MOD <= int.max, format("MOD must satisfy MOD*MOD <= long.max. Now MOD = %s.", MOD));
}
do {
    return mod_pow(x, MOD-2, MOD);
}

long mod_pow (long a, long x, const long MOD)
in {
    assert(0 <= x, "x must satisfy 0 <= x");
    assert(1 <= MOD, "MOD must satisfy 1 <= MOD");
    assert(MOD <= int.max, "MOD must satisfy MOD*MOD <= long.max");
}
do {
    // normalize
    a %= MOD; a += MOD; a %= MOD;

    long res = 1L;
    long base = a;
    while (0 < x) {
        if (0 < (x&1)) (res *= base) %= MOD;
        (base *= base) %= MOD;
        x >>= 1;
    }

    return res % MOD;
}

class UnionFind_Array {
    /*
     * VERYFYIED
     *   - uniteとsame : yosupo judge (https://judge.yosupo.jp/problem/unionfind)
     *
     * UNVERYFYIED
     *   - countGroups
     *   - GroupSize
     *   - enumGroups
     */
    private:
        int N;
        int[] parent;
        int[] size;

    this (int N)
    in {
        assert(0 <= N, "N must be positive integer.");
    }
    do {
        this.N = N;
        parent = new int[](N);
        size = new int[](N);
        foreach (i; 0..N) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int root (int x)
    in {
        assert(0 <= x && x < N);
    }
    do {
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    bool same (int x, int y)
    in {
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
    }
    do {
        return root(x) == root(y);
    }

    void unite (int x, int y)
    in {
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
    }
    do {
        int larger, smaller;
        if (GroupSize(x) <= GroupSize(y)) {
            larger = root(y);
            smaller = root(x);
        } else {
            larger = root(x);
            smaller = root(y);
        }

        if (larger == smaller) return;

        parent[smaller] = larger;
        size[larger] += size[smaller];
    }

    int countGroups () {
        int res = 0;
        foreach (i; 0..N) if (root(i) == i) res++;
        return res;
    }

    int GroupSize (int x)
    in {
        assert(0 <= x && x < N);
    }
    do {
        return size[root(x)];
    }

    int[][] enumGroups (int x)
    in {
        assert(0 <= x && x < N);
    }
    do {
        int[][] mp = new int[][](N, 0);
        foreach (i; 0..N) {
            mp[root(i)] ~= i;
        }

        int[][] res;
        foreach (m; mp) {
            if (m.length == 0) continue;
            res ~= m;
        }

        return res;
    }

    void reset (int N = this.N)
    in {
        assert(0 <= N, "N must be positive integer.");
    }
    do {
        if (N != this.N) {
            this.N = N;
            parent.length = size.length = N;
        }

        foreach (i; 0..N) {
            parent[i] = i;
            size[i] = 1;
        }
    }
}

auto UnionFind (int N) {
    return new UnionFind_Array(N);
}