#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
const int maxn=2e5+10;
const int maxm=1e5+10;
const int mod=1000002022;
int n,m;
vector<vi> graph(maxn);
vl mul(maxn,1);
vl vals(maxm,0);
void dfs(int cur) {
mul[cur]=max(1,(int)graph[cur].size());
for (auto to:graph[cur]) {
dfs(to);
mul[cur]=(mul[cur]*mul[to])%mod;
}
}
void dfs2(int cur, ll mult=1) {
if (graph[cur].size()==0) {
vals[cur-n]=mult;
return;
}
vl pref(graph[cur].size()+1,1),suff(graph[cur].size()+1,1);
for (int i=0; i<graph[cur].size(); i++) {
pref[i+1]=mul[graph[cur][i]]*pref[i]%mod;
suff[graph[cur].size()-i-1]=mul[graph[cur][graph[cur].size()-i-1]]*suff[graph[cur].size()-i]%mod;
}
for (int i=0; i<graph[cur].size(); i++) {
dfs2(graph[cur][i],(mult*pref[i]%mod)*suff[i+1]%mod);
}
}
struct SegTree {
struct Node {
ll sum=0,actsum=0;
bool flip=0;
Node(ll _sum=0, ll _actsum=0): sum(_sum),actsum(_actsum) {}
};
Node unite(Node a, Node b) {
return {(a.sum+b.sum)%mod,(a.actsum+b.actsum)%mod};
}
vector<Node> tree;
int sze;
void push(int v, int tl, int tr) {
if (tree[v].flip) {
tree[v].actsum=(tree[v].sum-tree[v].actsum+mod)%mod;
if (tl!=tr) {
tree[v*2].flip^=1;
tree[v*2+1].flip^=1;
}
tree[v].flip=0;
}
}
void init(int _sze, vl& vals, vi& onoff) {
sze=_sze;
tree.resize(4*sze);
build(vals,onoff,1,0,sze-1);
}
void build(vl& vals, vi& onoff, int v, int tl, int tr) {
if (tl==tr) {
if (onoff[tl]) {
tree[v]={vals[tl],vals[tl]};
}
else {
tree[v]={vals[tl],0};
}
return;
}
int tm=tl+(tr-tl)/2;
build(vals,onoff,v*2,tl,tm);
build(vals,onoff,v*2+1,tm+1,tr);
tree[v]=unite(tree[v*2],tree[v*2+1]);
}
void flip(int l, int r, int v, int tl, int tr) {
push(v,tl,tr);
if (r<tl || l>tr) {
return;
}
if (l<=tl && tr<=r) {
tree[v].flip=1;
push(v,tl,tr);
return;
}
int tm=tl+(tr-tl)/2;
flip(l,r,v*2,tl,tm);
flip(l,r,v*2+1,tm+1,tr);
tree[v]=unite(tree[v*2],tree[v*2+1]);
}
void flip(int l, int r) {
flip(l,r,1,0,sze-1);
}
ll get() {
return tree[1].actsum;
}
};
SegTree dat;
void init(int nn, int mm, vi parent, vi onoff) {
n=nn;
m=mm;
for (int i=1; i<n+m; i++) {
graph[parent[i]].pb(i);
}
dfs(0);
dfs2(0);
dat.init(m,vals,onoff);
}
int count_ways(int l, int r) {
dat.flip(l-n,r-n);
return dat.get();
}
