#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1000'000'000 + 2022;

int N, M;
vector<int> S, A;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    ::N = N, ::M = M, ::A = A;
    S.resize(M);
    vector<vector<int>> adj(N + M);
    for (int i = 1; i < N + M; ++i) {
        adj[P[i]].push_back(i);
    }
    vector<int> dp(N + M);
    auto dfs1 = [&](auto self, int v) -> void {
        if (v >= N) {
            dp[v] = 1;
            return;
        }
        dp[v] = size(adj[v]);
        for (int to : adj[v]) {
            self(self, to);
            dp[v] = 1LL * dp[v] * dp[to] % MOD;
        }
    };
    dfs1(dfs1, 0);
    auto dfs2 = [&](auto self, int v, int cnt) -> void {
        if (v >= N) {
            S[v - N] = cnt;
            return;
        }
        vector<int> pref(size(adj[v]) + 1, 1), suf(pref);
        for (int i = 0; i < size(adj[v]); ++i) {
            pref[i + 1] = 1LL * pref[i] * dp[adj[v][i]] % MOD;
            suf[i] = dp[adj[v][i]];
        }
        for (int i = size(adj[v]) - 1; i >= 0; --i) {
            suf[i] = 1LL * suf[i + 1] * suf[i] % MOD;
        }
        for (int i = 0; i < size(adj[v]); ++i) {
            self(self, adj[v][i], 1LL * cnt * pref[i] % MOD * suf[i + 1] % MOD);
        }
    };
    dfs2(dfs2, 0, 1);
}

int count_ways(int L, int R) {
    L -= N, R -= N;
    int ans = 0;
    for (int i = L; i <= R; ++i) {
        A[i] ^= 1;
    }
    for (int i = 0; i < M; ++i) {
        if (A[i]) {
            ans += S[i];
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
    }
    return ans;
}