#include "circuit.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "stub.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define PI 2*acos(0.0)
const ll mod = 1000002022;
ll add(ll a, ll b) {
return ((a + b) % mod + mod) % mod;
}
ll mult(ll a, ll b) {
return ((a * b) % mod + mod) % mod;
}
const int N = 2e5 + 7;
ll tree[2][N * 4], lz[N * 4]; // 0 - all configurations; 1 - valid configurations;
vector <int> graph[N];
vector <ll> pref[N], suff[N];
int n, m;
vector <int> parent, state;
ll valid_for[N], ans_for[N];
ll dfs(int v) {
valid_for[v] = max(1, sz(graph[v]));
for (auto to : graph[v]) {
valid_for[v] = mult(valid_for[v], dfs(to));
}
return valid_for[v];
}
void calc(int v, ll val) {
ans_for[v] = val;
for (int i = 0; i < sz(graph[v]); i++) {
auto to = graph[v][i];
calc(to, mult(val, mult((i == 0 ? 1ll : pref[v][i - 1]), (i == sz(graph[v]) - 1ll ? 1 : suff[v][i + 1]))));
}
}
void build(int v, int l, int r) {
if (l == r) {
tree[0][v] = ans_for[l + n];
if (state[l]) {
tree[1][v] = ans_for[l + n];
}
return;
}
int mid = (l + r) >> 1;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
tree[0][v] = add(tree[0][v * 2], tree[0][v * 2 + 1]);
tree[1][v] = add(tree[1][v * 2], tree[1][v * 2 + 1]);
}
void push(int v, int l, int r) {
if (lz[v]) {
tree[1][v] = tree[0][v] - tree[1][v];
if (l != r) {
lz[v * 2] ^= lz[v];
lz[v * 2 + 1] ^= lz[v];
}
lz[v] = 0;
}
}
void update(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (ql > r || l > qr) return;
if (ql <= l && r <= qr) {
lz[v] ^= 1;
push(v, l, r);
return;
}
int mid = (l + r) >> 1;
update(v * 2, l, mid, ql, qr);
update(v * 2 + 1, mid + 1, r, ql, qr);
tree[1][v] = add(tree[1][v * 2], tree[1][v * 2 + 1]);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M, parent = P, state = A;
for (int i = 1; i < n + m; i++) {
graph[parent[i]].pb(i);
}
dfs(0);
for (int i = 0; i < n + m; i++) {
for (auto to : graph[i]) {
pref[i].pb(valid_for[to]);
suff[i].pb(valid_for[to]);
}
for (int j = 1; j < sz(pref[i]); j++) {
pref[i][j] = mult(pref[i][j], pref[i][j - 1]);
}
for (int j = sz(suff[i]) - 2; j >= 0; j--) {
suff[i][j] = mult(suff[i][j], suff[i][j + 1]);
}
}
calc(0, 1);
build(1, 0, m - 1);
}
int count_ways(int L, int R) {
update(1, 0, m - 1, L - n, R - n);
return tree[1][1];
}
