#include "circuit.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const Int MOD = 1e9+2022;
const int N = 1e5+5;
int n, m;
V<int> p;
#define mid (tl+tr)/2
#define lc v+1
#define rc v+2*(mid-tl+1)
struct Multree{
Int st[4*N];
Multree(){
rep(i,0,4*N) st[i] = 1;
}
void upd(int l,int r,int x,int v=0,int tl=0,int tr=n+m-1){
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
(st[v] *= x )%=MOD; return;
}
upd(l,r,x, lc,tl,mid);
upd(l,r,x, rc,mid+1,tr);
}
Int qry(int i,int v=0,int tl=0,int tr=n+m-1){
if(tl==tr) return st[v];
if(i<=mid) return st[v] *qry(i, lc,tl,mid)%MOD ;
else return st[v] *qry(i, rc,mid+1,tr)%MOD;
}
} multree;
struct Fliptree{
int st[2*N][2];
bool lz[2*N];
void assign(int i,int x,int v=0,int tl=0,int tr=m-1){
if(tl==tr){
st[v][0] = x; return;
}
if(i<=mid) assign(i,x, lc,tl,mid);
else assign(i,x, rc,mid+1,tr);
rep(i,0,2)
(st[v][i] = st[lc][i] + st[rc][i] )%=MOD;
}
void flip(int l,int r,int v=0,int tl=0,int tr=m-1){
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
swap(st[v][0], st[v][1]);
lz[v] ^= 1; return;
}
if(lz[v]){
flip(tl,tr, lc,tl,mid);
flip(tl,tr, rc,mid+1,tr);
lz[v] = 0;
}
flip(l,r, lc,tl,mid);
flip(l,r, rc,mid+1,tr);
rep(i,0,2)
(st[v][i] = st[lc][i] + st[rc][i] )%=MOD;
}
int qry(){
return st[0][1];
}
} fliptree;
V<int> adj[2*N];
int in[2*N], out[2*N], timer=0;
Int dp[2*N];
void dfs(int x=0){
in[x] = timer++;
if(adj[x].size()==0) dp[x] = 1;
else dp[x] = adj[x].size();
for(int y : adj[x]){
dfs(y);
(dp[x] *= dp[y] )%=MOD;
}
out[x] = timer-1;
}
void init(int _n,int _m,V<int> _p,V<int> a){
n = _n; m = _m; p.swap(_p);
rep(i,1,n+m){
adj[p[i]].push_back(i);
}
dfs();
rep(i,1,n+m){
// dbg(i); dbg(dp[i]);
// dbg(in[i]); dbg(out[i]);
if(in[p[i]]+1 <= in[i]-1){
// cout << in[p[i]]+1 _ in[i]-1 << nl;
multree.upd(in[p[i]]+1,in[i]-1, dp[i]);
}
if(out[i]+1 <= out[p[i]]){
// cout << out[i]+1 _ out[p[i]] << nl;
multree.upd(out[i]+1, out[p[i]], dp[i]);
}
// cout << nl;
}
rep(i,0,m){
// dbg(in[n+i]);
// dbg(multree.qry(in[n+i]));
fliptree.assign(i, multree.qry(in[n+i]));
if(a[i]){
fliptree.flip(i,i);
}
}
// dbg(fliptree.qry());
}
int count_ways(int l,int r){
// return -1;
l -= n; r -= n;
fliptree.flip(l, r);
return fliptree.qry();
}
