#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else

#endif

#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;
vector<int> d;
vector<array<ll, 2>> t;
bool bintree;

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

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

void apply(int v) {
    d[v] ^= 1;
    swap(t[v][0], t[v][1]);
}

void push(int v) {
    if (d[v]) {
        apply(v + v + 1);
        apply(v + v + 2);
        d[v] = 0;
    }
}

void upd(int v) {
    array<ll, 2> dp = {0, 1};
    ll sm_cnt = (int)g[v].size();
    for (auto to : g[v]) {
        auto [cnt0, cnt1] = t[to];
        ll cnt01 = (cnt0 + cnt1) % mod;
        array<ll, 2> ndp = {0, 0};
        ndp[0] = (dp[0] * cnt01 + dp[1] * cnt1) % mod;
        ndp[1] = dp[1] * cnt01 % mod;
        ndp.swap(dp);
        sm_cnt = (sm_cnt * cnt01) % mod;
    }
    ll cnt1 = dp[0];
    ll cnt0 = (sm_cnt + mod - cnt1) % mod;
    t[v] = {cnt0, cnt1};
}

void build_bintree() {
    d.assign(n + m, 0);
    t.assign(n + m, {0, 0});
    for (int i = 0; i < m; i += 1) {
        t[n + i][a[i]] += 1;
    }
    for (int i = n - 1; i >= 0; i -= 1) {
        upd(i);
    }
}

void chng_bintree(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) {
        return;
    }
    if (l <= tl && tr <= r) {
        apply(v);
        return;
    }
    int tm = (tl + tr) / 2;
    push(v);
    chng_bintree(v + v + 1, tl, tm, l, r);
    chng_bintree(v + v + 2, tm + 1, tr, l, r);
    upd(v);
}

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);
    }
    bintree = (m == n + 1);
	ll x = 1;
	while(x < m){
		x *= 2;
	}
	if(x != m){
		bintree = false;
	}
    for (int i = 1; i < n + m; i += 1) {
        if (prnt[i] != (i - 1) / 2) {
            bintree = false;
            break;
        }
    }
    if (bintree) {
        build_bintree();
        return;
    }
}

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