#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define L(node) node * 2
#define R(node) node * 2 + 1
#define ll long long
const int modulo = 1000002022;
vector<int> adj[2000005];
int sz[400005], arr[400005], tree[2000005 * 4], tree2[2000005 * 4], lazy[2000005 * 4];
int n, m;
ll add(ll a, ll b)
{
return (a + b) % modulo;
}
ll subs(ll a, ll b)
{
return (((a - b) % modulo) + modulo) % modulo;
}
ll mul(ll a, ll b)
{
return (a * b) % modulo;
}
int dfs(int node, int root)
{
if (adj[node].empty()) return sz[node] = 1;
sz[node] = 2;
for (auto i : adj[node])
sz[node] = mul(sz[node], dfs(i, node));
return sz[node];
}
void dfs2(int node, int root, int val)
{
arr[node] = val;
if (adj[node].empty())
{
return;
}
dfs2(adj[node][1], node, mul(val, sz[adj[node][0]]));
dfs2(adj[node][0], node, mul(val, sz[adj[node][1]]));
}
void build(int node, int l, int r)
{
if (l == r)
{
tree[node] = arr[l - 1];
return;
}
int mid = (l + r) / 2;
build(L(node), l, mid);
build(R(node), mid + 1, r);
tree[node] = add(tree[L(node)], tree[R(node)]);
}
void push(int node, int l, int r)
{
if (lazy[node] == 0) return;
tree2[node] = subs(tree[node], tree2[node]);
lazy[node] = 0;
if (l == r)
return;
lazy[L(node)] ^= 1;
lazy[R(node)] ^= 1;
}
void update(int node, int l, int r, int sl, int sr)
{
push(node, l, r);
if (l > r || l > sr || r < sl) return;
int mid = (l + r) / 2;
if (l >= sl && r <= sr)
{
lazy[node] ^= 1;
push(node, l, r);
return;
}
push(node, l, r);
update(L(node), l, mid, sl, sr);
update(R(node), mid + 1, r, sl, sr);
tree2[node] = add(tree2[L(node)], tree2[R(node)]);
}
int sum(int node, int l, int r, int sl, int sr)
{
push(node, l, r);
if (l > r || l > sr || r < sl) return 0;
if (l >= sl && r <= sr) return tree2[node];
int mid = (l + r) / 2;
return add(sum(L(node), l, mid, sl, sr), sum(R(node), mid + 1, r, sl, sr));
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n = N, m = M;
for (int i = 1; i < N + M; i++)
adj[P[i]].pb(i);
int tmp = dfs(0, -1);
dfs2(0, -1, 1);
build(1, 1, N + M);
for (int i = 0; i < M; i++)
if (A[i]) update(1, 1, N + M, N + i + 1, N + i + 1);
}
int count_ways(int L, int R)
{
update(1, 1, n + m, L + 1, R + 1);
return sum(1, 1, n + m, 1, n + m);
}
