#include "circuit.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
constexpr ll mod = 1'000'002'022;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"
struct lazy_segment_tree{
ll N;
vi node;
vector<bool> flag;
vi sum;
lazy_segment_tree(ll n, vi s, vi a){
N = 1;
while(N <= n) N *= 2;
node.resize(2*N);
flag.resize(2*N);
sum.resize(2*N);
rep(i,0,n) sum[i+N] = s[i];
per(i,N-1,1) sum[i] = (sum[i*2]+sum[i*2+1])%mod;
rep(i,0,n) node[i+N] = s[i]*a[i];
per(i,N-1,1) node[i] = (node[i*2]+node[i*2+1])%mod;
};
void eval(ll now){
if(flag[now]){
node[now] = sum[now]-node[now];
if(now < N){
flag[now*2] = !flag[now*2];
flag[now*2+1] = !flag[now*2+1];
}
flag[now] = false;
}
}
void update(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(a <= l && r <= b){
flag[now] = !flag[now];
eval(now);
return;
}
if(r <= a || b <= l) return;
update(a,b,now*2,l,(l+r)/2);
update(a,b,now*2+1,(l+r)/2,r);
node[now] = (node[now*2]+node[now*2+1])%mod;
}
ll calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(a <= l && r <= b) return node[now];
if(r <= a || b <= l) return 0;
return (calc(a,b,now*2,l,(l+r)/2)+calc(a,b,now*2+1,(l+r)/2,r))%mod;
}
};
vi sum;
vii edge;
vi A;
ll N,M;
lazy_segment_tree seg(0,vi(),vi());
void init(int n, int m, std::vector<int> P, std::vector<int> a) {
N = n, M = m;
sum.resize(N+M,1);
edge.resize(N+M);
A.resize(N+M);
rep(i,0,M) A[i+N] = a[i];
rep(i,1,N+M){
edge[P[i]].pb(i);
}
vi sum2(N+M);
std::function<void(ll)> dfs1 = [&](ll now){
sum2[now] = edge[now].size();
sum2[now] = std::max(sum2[now], 1ll);
for(auto next: edge[now]){
dfs1(next);
sum2[now] *= sum2[next];
sum2[now] %= mod;
}
};
dfs1(0);
std::function<void(ll)> dfs2 = [&](ll now){
ll len = edge[now].size();
vi l(len+1,1), r(len+1,1);
rep(i,0,len){
l[i+1] = l[i]*sum2[edge[now][i]]%mod;
}
per(i,len-1,0){
r[i] = r[i+1]*sum2[edge[now][i]]%mod;
}
rep(i,0,len){
ll next = edge[now][i];
sum[next] = sum[now]*l[i]%mod*r[i+1]%mod;
dfs2(next);
}
};
dfs2(0);
vi sum_(M);
rep(i,0,M) sum_[i] = sum[i+N];
vi A_(M);
rep(i,0,M) A_[i] = a[i];
lazy_segment_tree seg2(M,sum_,A_);
seg = seg2;
}
int count_ways(int L, int R) {
L -= N;
R -= N;
seg.update(L,R+1);
ll ans = seg.calc(0,M);
if(ans < 0) ans += mod;
ans %= mod;
return ans;
}
