#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
const ll mod=1000002022;
#include "circuit.h"
struct segtree{
ll N=1;
vi seg,lazy,sum;
ll f(ll a,ll b){
return (a+b)%mod;
}
void init(vi a,vi b){
while(N<a.size())N<<=1;
seg=vi(N*2);lazy=vi(N*2);sum=vi(N*2);
rep(i,a.size()){
sum[i+N]=a[i];
seg[i+N]=a[i]*b[i];
}
for(ll i=N-1;i>0;i--){
sum[i]=f(sum[i*2],sum[i*2+1]);
seg[i]=f(seg[i*2],seg[i*2+1]);
}
}
void eval(ll k,ll l,ll r){
if(!lazy[k])return;
seg[k]=(sum[k]-seg[k])%mod;
if(r-l>1)rep(t,2)lazy[k*2+t]^=1;
lazy[k]=0;
}
ll get(){
eval(1,0,N);
return seg[1];
}
void upd(ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=N;
if(a<=l&&r<=b){
lazy[k]^=1;eval(k,l,r);return;
}
if(r<=a||b<=l){
eval(k,l,r);return;
}
eval(k,l,r);
upd(a,b,k*2,l,(l+r)/2);
upd(a,b,k*2+1,(l+r)/2,r);
seg[k]=f(seg[k*2],seg[k*2+1]);
}
};
segtree seg;
ll n,N_;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
N_=N;
vvi ch(N+M);
REP(i,1,N+M)ch[P[i]].pb(i);
vi prod(N+M,1);
for(ll i=N-1;i>=0;i--){
prod[i]=ch[i].size();
for(ll x:ch[i])prod[i]=prod[i]*prod[x]%mod;
}
vi dp(N+M,1);
rep(i,N){
vi tl(ch[i].size()+1,1),tr(ch[i].size()+1,1);
rep(j,ch[i].size())tl[j+1]=tl[j]*prod[ch[i][j]]%mod;
for(ll j=ch[i].size()-1;j>=0;j--)tr[j]=tr[j+1]*prod[ch[i][j]]%mod;
rep(j,ch[i].size())dp[ch[i][j]]=dp[i]*tl[j]%mod*tr[j+1]%mod;
}
n=M;
vi a(n),b(n);
rep(i,n)a[i]=dp[N+i];
rep(i,n)b[i]=A[i];
seg.init(a,b);
}
int count_ways(int L, int R) {
ll l=L-N_,r=R+1-N_;
seg.upd(l,r);
ll ans=seg.get();
if(ans<0)ans+=mod;
return ans;
}
