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

using namespace std;

typedef long long ll;

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

void dfs1(ll v, vector<vector<ll>>& sons, vector<ll>& scf) {
	if (v >= sons.size()) {
		scf[v] = 1;
		return;
	}
	scf[v] = sons[v].size();
	for (auto i : sons[v]) {
		dfs1(i, sons, scf);
		scf[v] = scf[v] * scf[i] % MOD;
	}
}

void dfs(ll v, vector<vector<ll>>& sons, vector<ll>& cf, vector<ll>& scf, ll ncf) {
	if (v >= sons.size()) {
		cf[v - sons.size()] = ncf;
		return;
	}
	vector<ll> pcf(1, 1);
	for (auto i : sons[v]) {
		ll nmul = scf[i];
		pcf.push_back(pcf.back() * nmul % MOD);
	}
	ll muln = 1;
	reverse(sons[v].begin(), sons[v].end());
	for (auto i : sons[v]) {
		ll nmul = scf[i];
		pcf.pop_back();
		dfs(i, sons, cf, scf, ncf * muln % MOD * pcf.back() % MOD);
		muln = muln * nmul % MOD;
	}	
}

vector<int> na;
vector<ll> ncf;
ll nn;

void init(int n, int m, vector<int> p, vector<int> a) {
	vector<vector<ll>> sons(n);
	for (ll i = 1; i < n + m; i++) {
		sons[p[i]].push_back(i);
	}
	vector<ll> cf(m), scf(n + m);
	dfs1(0, sons, scf);
	dfs(0, sons, cf, scf, 1);
	na = a;
	ncf = cf;
	nn = n;
}

int count_ways(int l, int r) {
	l -= nn;
	r -= nn;
	for (ll i = l; i <= r; i++) {
		na[i] ^= 1;
	}
	ll ans = 0;
	for (ll i = 0; i < na.size(); i++) {
		ans += ncf[i] * na[i];
		ans %= MOD;
	}
	return ans;
}