#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<18;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1000002022;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n;
vi graf[N];
ll dp[N],il[N],seg[(SS<<1)+10][2];
bool lazy[(SS<<1)+10],wl[N];
void dfs1(int v){
il[v]=graf[v].size();
if(graf[v].size()==0) il[v]=1;
for(auto u:graf[v]){
dfs1(u);
(il[v]*=il[u])%=mod;
}
}
void dfs2(int v,ll val){
vector<ll> xd(graf[v].size()+1);
dp[v]=val;
xd[graf[v].size()]=1;
for(int i2=graf[v].size()-1;i2>=0;i2--){
xd[i2]=xd[i2+1]*il[graf[v][i2]];
xd[i2]%=mod;
}
ll curr=1;
for(int i2=0;i2<graf[v].size();i2++){
auto u=graf[v][i2];
dfs2(u,(((val*curr)%mod)*xd[i2+1])%mod);
(curr=curr*il[u])%=mod;
}
}
void push(int v){
if(lazy[v]){
lazy[v]=0;
lazy[(v<<1)]^=1,lazy[(v<<1)+1]^=1;
swap(seg[(v<<1)+1][0],seg[(v<<1)+1][1]);
swap(seg[(v<<1)][0],seg[(v<<1)][1]);
}
}
void upd(int a,int b,int p=0,int k=SS-1,int v=1){
if(p>b or k<a) return;
if(p>=a and k<=b){
lazy[v]^=1;
swap(seg[v][0],seg[v][1]);
return;
}
push(v);
int sr=(p+k)>>1;
upd(a,b,p,sr,(v<<1)),upd(a,b,sr+1,k,(v<<1)+1);
(seg[v][0]=seg[(v<<1)][0]+seg[(v<<1)+1][0])%=mod;
(seg[v][1]=seg[(v<<1)][1]+seg[(v<<1)+1][1])%=mod;
}
void uzu(int v){
if(v>=SS){
if(wl[v-SS]) seg[v][1]=dp[v-SS+n];
else seg[v][0]=dp[v-SS+n];
return;
}
uzu((v<<1)),uzu((v<<1)+1);
(seg[v][0]=seg[(v<<1)][0]+seg[(v<<1)+1][0])%=mod;
(seg[v][1]=seg[(v<<1)][1]+seg[(v<<1)+1][1])%=mod;
}
void init(int n2,int m,vi p,vi a){
n=n2;
for(int i=1;i<n+m;i++) graf[p[i]+1].push_back(i+1);
dfs1(1);
dfs2(1,1);
for(int i=0;i<a.size();i++) wl[i+1]=a[i];
uzu(1);
}
int count_ways(int l,int r){
l++,r++;
l-=n,r-=n;
upd(l,r);
return seg[1][1];
}
/*int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int n2,m2,q;
cin>>n2>>m2>>q;
vi p,a;
for(int i=0;i<n2+m2;i++){
int d;
cin>>d;
p.push_back(d);
}
for(int i=0;i<m2;i++){
int d;
cin>>d;
a.push_back(d);
}
init(n2,m2,p,a);
while(q--){
int l,r;
cin>>l>>r;
cout<<count_ways(l,r)<<"\n";
}
}*/
