#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const long long MD = 1e9+2022;
template<long long MOD=MD> struct mdint {
int d=0;
mdint () {d=0;}
mdint (long long _d) : d(_d%MOD){
if(d<0) d+=MOD;
};
friend mdint& operator+=(mdint& a, const mdint& o) {
a.d+=o.d; if(a.d>=MOD) a.d-=MOD;
return a;
}
friend mdint& operator-=(mdint& a, const mdint& o) {
a.d-=o.d; if(a.d<0) a.d+=MOD;
return a;
}
friend mdint& operator*=(mdint& a, const mdint& o) {
return a = mdint((ll)a.d*o.d);
}
mdint operator*(const mdint& o) const {
mdint res = *this;
res*=o;
return res;
}
mdint operator+(const mdint& o) const {
mdint res = *this;
res+=o;
return res;
}
mdint operator-(const mdint& o) const {
mdint res = *this;
res-=o;
return res;
}
mdint operator^(long long b) const {
mdint tmp = 1;
mdint power = *this;
while(b) {
if(b&1) {
tmp = tmp*power;
}
power = power*power;
b/=2;
}
return tmp;
}
bool operator==(const mdint& o) { return d==o.d;}
bool operator!=(const mdint& o) { return d!=o.d;}
friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;}
friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;}
};
using mint = mdint<MD>;
struct segtree {
struct node {
mint res[2] = {};
bool flip=0;
node() {}
};
vector<node> seg;
int n,ptwo;
segtree() {}
segtree(int nn) {
n=nn,ptwo=1;
while(ptwo<n) ptwo*=2;
seg.resize(2*ptwo);
}
void puttag(int i, bool f) {
auto& v = seg[i];
if(f) {
swap(v.res[0],v.res[1]);
v.flip^=1;
}
}
void pull(int i) {
auto& v = seg[i];
v.res[0] = seg[i*2].res[0]+seg[i*2+1].res[0];
v.res[1] = seg[i*2].res[1]+seg[i*2+1].res[1];
}
void push(int i) { // TODO!
auto& v = seg[i];
if(v.flip) {
puttag(i*2,v.flip);
puttag(i*2+1,v.flip);
}
v.flip=false;
}
void set(int i, int l, int r, int ql, int qr) {
if(qr<l or r<ql) return;
if(ql<=l and r<=qr) {
puttag(i,1); // correct?
return;
}
int mid = (l+r)/2;
push(i);
set(i*2,l,mid,ql,qr),set(i*2+1,mid+1,r,ql,qr);
pull(i);
}
void set(int l, int r) {
set(1,0,ptwo-1,l,r);
}
node& operator[](int i) {return seg[i+ptwo];}
void build() {
for(int i=ptwo-1;i>=1;--i) {
pull(i);
}
}
};
segtree seg;
int n;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
vvi adj(N+M);
for(int i=1;i<N+M;++i) {
adj[P[i]].push_back(i);
}
vector<mint> degProd(N+M,1);
for(int i=N-1;i>=0;--i) {
degProd[i]=adj[i].size();
for(int to : adj[i]) {
degProd[i]*=degProd[to];
}
}
vector<mint> w(N+M,1);
for(int i=0;i<N;++i) {
int c = adj[i].size();
vector<mint> pref(c+1,1);
for(int j=1;j<=c;++j) {
pref[j]=pref[j-1]*degProd[adj[i][j-1]];
}
mint suf=1;
for(int j=c-1;j>=0;--j) {
w[adj[i][j]]=w[i]*pref[j]*suf;
suf*=degProd[adj[i][j]];
}
}
seg = segtree(M);
for(int i=0;i<M;++i) {
seg[i].res[A[i]] = w[i+N];
}
seg.build();
}
int count_ways(int L, int R) {
seg.set(L-n,R-n);
return seg.seg[1].res[1].d;
}
