#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 100005
const int modulo = 1000002022;
const ll INF = 2e18 + 7;
int add(ll a, ll b){
if (a + b < modulo) return a + b;
return a + b - modulo;
}
int subs(ll a, ll b){
if (a < b) return a - b + modulo;
return a - b;
}
int mul(ll a, ll b){
return (a * b) % modulo;
}
int fe(ll a, ll b){
if (b == 0) return 1;
if (b % 2) return mul(a, fe(a, b - 1));
int tmp = fe(a, b / 2);
return mul(tmp, tmp);
}
struct SegTree{
vector<int> t, lazy, arr, sum;
int n;
void build(int node, int l, int r){
if (l == r){
sum[node] = arr[l];
t[node] = 0;
return;
}
int mid = (l + r) / 2;
build(LL, l, mid);
build(RR, mid + 1, r);
sum[node] = add(sum[LL], sum[RR]);
t[node] = 0;
}
void push(int node, int l, int r){
if (lazy[node] == 0) return;
t[node] = subs(sum[node], t[node]);
lazy[node] = 0;
if (l != r) lazy[LL] ^= 1, lazy[RR] ^= 1;
}
void update(int node, int l, int r, int sl, int sr){
push(node, l, r);
if (l > sr || r < sl) return;
if (l >= sl && r <= sr){
lazy[node] ^= 1;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
update(LL, l, mid, sl, sr);
update(RR, mid + 1, r, sl, sr);
t[node] = add(t[LL], t[RR]);
}
int query(int node, int l, int r, int sl, int sr){
push(node, l, r);
if (l > sr || r < sl) return 0;
if (l >= sl && r <= sr) return t[node];
int mid = (l + r) / 2;
return add(query(LL, l, mid, sl, sr), query(RR, mid + 1, r, sl, sr));
}
SegTree(int N, vector<int> a){
n = N;
t.resize(4 * n + 5, 0), lazy.resize(4 * n + 5, 0), sum.resize(4 * n + 5, 0);
arr = a;
build(1, 0, n - 1);
}
};
vector<int> adj[MAXN];
vector<int> pre[MAXN], suf[MAXN];
int val[MAXN], sz[MAXN], n, m;
void dfs(int node){
sz[node] = max((int)1, (int)adj[node].size());
pre[node].resize(adj[node].size());
suf[node].resize(adj[node].size());
for (auto i : adj[node]){
dfs(i);
sz[node] = mul(sz[node], sz[i]);
}
if (adj[node].empty()) return;
pre[node][0] = sz[adj[node][0]];
suf[node][(int)adj[node].size() - 1] = sz[adj[node].back()];
for (int i = 1; i < adj[node].size(); i++)
pre[node][i] = mul(pre[node][i - 1], sz[adj[node][i]]);
for (int i = (int)adj[node].size() - 2; i >= 0; i--)
suf[node][i] = mul(suf[node][i + 1], sz[adj[node][i]]);
}
void dfs2(int node, int x){
val[node] = x;
if (adj[node].empty()) return;
for (int i = 0; i < adj[node].size(); i++){
int m = 1;
if (i > 0) m = mul(m, pre[node][i - 1]);
if (i + 1 < adj[node].size()) m = mul(m, suf[node][i + 1]);
dfs2(adj[node][i], mul(x, m));
}
}
SegTree *T;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
for (int i = 1; i < n + m; i++)
adj[P[i]].pb(i);
dfs(0);
dfs2(0, 1);
vector<int> arr(m);
for (int i = 0; i < m; i++) arr[i] = val[i + n];
T = new SegTree(m, arr);
for (int i = 0; i < m; i++)
if (A[i]) T->update(1, 0, m - 1, i, i);
}
int count_ways(int L, int R) {
T->update(1, 0, m - 1, L - n, R - n);
return T->query(1, 0, m - 1, 0, m - 1);
}
/*
int main() {
fileio();
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
std::vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
assert(1 == scanf("%d", &P[i]));
}
for (int j = 0; j < M; ++j) {
assert(1 == scanf("%d", &A[j]));
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
assert(2 == scanf("%d %d", &L, &R));
printf("%d\n", count_ways(L, R));
}
return 0;
}
*/
