#include <bits/stdc++.h>

#include "circuit.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const ll inf = 1e18;
mt19937 rnd(234);

const ll mod = 1'000'002'022;

int n, m;
vector<vector<int>> g;
vector<int> a;
vector<int> prnt;

array<ll, 2> dfs_ways(int v) {
    if (v >= n) {
        array<ll, 2> rs = {0, 0};
        rs[a[v - n]] = 1;
        return rs;
    }
    array<ll, 2> dp = {0, 1};
    ll sm_cnt = (int)g[v].size();
    for (auto to : g[v]) {
        auto [cnt0, cnt1] = dfs_ways(to);
        array<ll, 2> ndp = {0, 0};
        ndp[0] = (dp[0] * (cnt0 + cnt1) % mod + dp[1] * cnt1 % mod) % mod;
        ndp[1] = dp[1] * (cnt0 + cnt1) % mod;
        ndp.swap(dp);
        sm_cnt = (sm_cnt * (cnt0 + cnt1)) % mod;
    }
    ll cnt1 = dp[0];
    ll cnt0 = (sm_cnt + mod - cnt1) % mod;
    return {cnt0, cnt1};
}

ll count_ways_dfs() {
    auto [cnt0, cnt1] = dfs_ways(0);
    return cnt1;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    prnt = P;
    a = A;
    g.assign(n + m, vector<int>());
    for (int i = 1; i < n + m; i += 1) {
        g[prnt[i]].push_back(i);
    }
}

int count_ways(int L, int R) {
    int l = L - n;
    int r = R - n;
    for (int i = l; i <= r; i += 1) {
        a[i] ^= 1;
    }
    ll rs = count_ways_dfs();
    return rs;
}