//
// Created by adavy on 8/8/2023.
//
#include <vector>
//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
const int MOD = 1e9+2022; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
struct Modular {
int value;
static const int MOD_value = MOD;
Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}
friend Modular operator+(Modular a, Modular const b) { return a += b; }
friend Modular operator-(Modular a, Modular const b) { return a -= b; }
friend Modular operator-(Modular const a) { return 0 - a; }
friend Modular operator*(Modular a, Modular const b) { return a *= b; }
friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};
#include "circuit.h"
vector<vi> cd;
int n, m;
vector<Modular> V,W; //values, weights
void dfs1(int nd){
// calculate node weights
if (nd >= n){
W[nd] = 1;
return;
}
W[nd]=1;
trav(nei, cd[nd]){
dfs1(nei);
W[nd]*=W[nei];
}
W[nd]*=cd[nd].size();
}
void dfs2(int nd, Modular mpl){
if (nd>=n){
V[nd] = mpl; return;
}
vector<Modular> weights;
trav(nei, cd[nd]) weights.pb(W[nei]);
vector<Modular> left = {1}, right = {1};
F0R(i, weights.size()) left.pb(left.back()*weights[i]);
R0F(i, weights.size()) right.pb(right.back()*weights[i]);
F0R(i, cd[nd].size())
dfs2(cd[nd][i], mpl*left[i]*right[(cd[nd].size()-1)-i]);
}
vector<Modular> prefs = {0};
int ssz = 131072;
vector<Modular> seg(2*ssz,0); vi lz(2*ssz,0);
void pushdown(int rt, int tl, int tr){
if (lz[rt]){
seg[rt] = (prefs[tr+1]-prefs[tl])-seg[rt];
lz[rt] = 0;
if (tl!=tr){
lz[2*rt]^=1;
lz[2*rt+1]^=1;
}
}
}
void flip(int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (r<tl || l > tr ) return;
if (l<=tl && tr<=r) {
lz[rt]^=1;
pushdown(rt, tl, tr);
return;
}
int tm = (tl+tr)>>1;
flip(l, r, rt<<1, tl, tm);
flip(l, r, (rt<<1)+1,tm+1,tr);
seg[rt] = seg[rt<<1]+seg[(rt<<1)+1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
cd.rsz(N);
V.rsz(N + M);
W.rsz(N + M);
n = N;
m = M;
F0R(i, n + m) {
if (i != 0) cd[P[i]].pb(i);
}
// calculate node values, node weights
dfs1(0);
dfs2(0, 1);
FOR(i, n, n + m) {
prefs.pb(prefs.back() + V[i]);
}
while(prefs.size()<=ssz){
prefs.pb(prefs.back());
}
//trav(i, prefs) cout << i << " "; cout << endl;
F0R(i, A.size()){
if (A[i]) flip(i, i, 1, 0, ssz-1);
}
// cout << seg[1].value << endl;
}
int count_ways(int L, int R) {
L-=n; R-=n;
flip(L,R,1,0,ssz-1);
return seg[1].value;
}
/*
#include <cassert>
#include <cstdio>
#include <vector>
int main() {
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
std::vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
assert(1 == scanf("%d", &P[i]));
}
for (int j = 0; j < M; ++j) {
assert(1 == scanf("%d", &A[j]));
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
assert(2 == scanf("%d %d", &L, &R));
printf("%d\n", count_ways(L, R));
}
return 0;
}
*/
