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

using namespace std;

typedef long long ll;

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

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