#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'002'022;
int n, m;
struct segTree{
ll sum[800002], rev[800002], lazy[800002];
void init(int i, int l, int r, ll *A, vector<int> &B){
lazy[i] = 0;
if(l==r){
sum[i] = A[l], rev[i] = 0;
if(!B[l-n]) swap(sum[i], rev[i]);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A, B);
init(i*2+1, m+1, r, A, B);
sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
}
void propagate(int i, int l, int r){
if(!lazy[i]) return;
swap(sum[i], rev[i]);
if(l!=r) lazy[i*2] = !lazy[i*2], lazy[i*2+1] = !lazy[i*2+1];
lazy[i] = 0;
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum[i];
int m = (l+r)>>1;
return (query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e)) % MOD;
}
void update(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = 1;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e), update(i*2+1, m+1, r, s, e);
sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
}
} tree;
int par[200002];
vector<int> link[200002];
ll S[200002], W[200002];
void dfs(int x){
S[x] = max(1, (int)link[x].size());
for(auto y: link[x]){
dfs(y);
S[x] = (S[x] * S[y]) % MOD;
}
}
void dfs2(int x, ll up = 1){
int k = (int)link[x].size();
vector<ll> prf(k+1), suf(k+1);
prf[0] = suf[k] = 1;
for(int i=1; i<=k; i++) prf[i] = (prf[i-1] * S[link[x][i-1]]) % MOD;
for(int i=k-1; i>=0; i--) suf[i] = (suf[i+1] * S[link[x][i]]) % MOD;
W[x] = up;
for(int i=0; i<k; i++){
dfs2(link[x][i], up * prf[i] % MOD * suf[i+1] % MOD);
}
}
void init(int _n, int _m, vector<int> P, vector<int> A){
n = _n, m = _m;
for(int i=0; i<n+m; i++) par[i] = P[i], link[par[i]].push_back(i);
dfs(0);
dfs2(0);
tree.init(1, n, n+m-1, W, A);
}
int count_ways(int L, int R) {
tree.update(1, n, n+m-1, L, R);
return tree.query(1, n, n+m-1, n, n+m-1);
}
