#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll MOD = 1000002022;
int n, m;
ll p[10000001], sz[10000001], v[1000001], d1[2000001], d2[2000001];
bool lz[20000001];
vector<ll> d[1000001];
void dfs(int u)
{
for (auto v : d[u])
{
sz[v] = sz[u] + 1;
dfs(v);
}
}
void build(int l, int r, int i, vector<int> &t)
{
if (l == r)
{
if (t[l])
{
d1[i] = v[l];
}
else
{
d2[i] = v[l];
}
return;
}
int md = (l + r) / 2;
build(l, md, 2 * i, t);
build(md + 1, r, 2 * i + 1, t);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void lazy(int l, int r, int i)
{
if (!lz[i])
return;
lz[i] = 0;
swap(d1[i], d2[i]);
if (l == r)
return;
lz[2 * i] = !lz[2 * i];
lz[2 * i + 1] = !lz[2 * i + 1];
}
void update(int l, int r, int i, int ql, int qr)
{
lazy(l, r, i);
if (r < ql || qr < l)
return;
if (ql <= l && r <= qr)
{
lz[i] = 1;
lazy(l, r, i);
return;
}
int md = (l + r) / 2;
update(l, md, 2 * i, ql, qr);
update(md + 1, r, 2 * i + 1, ql, qr);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
p[0] = 1;
n = N;
m = M;
for (int i = 1; i < N + M; i++)
p[i] = (p[i - 1] * 2) % MOD;
for (int i = 1; i < N + M; i++)
d[P[i]].push_back(i);
dfs(0);
for (int i = N; i < N + M; i++)
v[i - N] = p[N - sz[i]];
build(0, M - 1, 1, A);
}
int count_ways(int L, int R)
{
update(0, m - 1, 1, L - n, R - n);
return d1[1];
}
