#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll md = 1000002022;
struct segtree{
struct node{
ll x = 0, sum = 0;
bool rev = 0;
node(){
}
node operator+(node X){
node rt;
rt.sum = (sum+X.sum)%md;
rt.x = (x+X.x)%md;
return rt;
}
void pushdown(node &X){
if(!rev) return;
X.rev^=rev;
X.x = (X.sum-X.x)%md;
}
};
int k;
vector<node> v;
segtree(const vector<ll>& sum){
int n = sum.size();
k = 1;
while(k < n) k*=2;
v.resize(2*k, node());
for(int i = k; i < k+n; i++) v[i].sum = sum[i-k];
for(int i = k-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
}
void update(int l, int r, int nd, int a, int b){
if(a > r || b < l) return;
if(a >= l && b <= r){
v[nd].rev^=1;
v[nd].x = v[nd].sum-v[nd].x;
return;
}
int mid = (a+b)/2;
v[nd].pushdown(v[2*nd]);
v[nd].pushdown(v[2*nd+1]);
v[nd].rev = 0;
update(l, r, 2*nd, a, mid);
update(l, r, 2*nd+1, mid+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
}
void update(int l, int r){
update(l, r, 1, 0, k-1);
}
int get(){
if(v[1].x < 0) v[1].x+=md;
return v[1].x;
}
};
int n, m;
vector<int> P, A;
vector<vector<int>> tree;
vector<ll> options, coefficient;
segtree s({});
void dfs(int nd){
if(nd >= n) return;
options[nd] = tree[nd].size();
for(int x: tree[nd]) dfs(x), options[nd]*=options[x], options[nd]%=md;
}
void dfs2(int nd, ll coeff){
if(nd >= n){
coefficient[nd-n] = coeff;
return;
}
int k = tree[nd].size();
vector<ll> pref, suff;
for(int x: tree[nd]) pref.pb(options[x]), suff.pb(options[x]);
for(int i = 1; i < k; i++) pref[i] = (pref[i]*pref[i-1])%md;
for(int i = k-2; i >= 0; i--) suff[i] = (suff[i]*suff[i+1])%md;
for(int i = 0; i < k; i++){
ll _coeff = coeff;
if(i) _coeff*=pref[i-1], _coeff%=md;
if(i != k-1) _coeff*=suff[i+1], _coeff%=md;
dfs2(tree[nd][i], _coeff);
}
}
void init(int _n, int _m, vector<int> _P, vector<int> _A){
swap(n, _n), swap(m, _m), swap(P, _P), swap(A, _A);
tree.resize(n+m);
for(int i = 1; i < n+m; i++) tree[P[i]].pb(i);
options.assign(n+m, 1);
coefficient.resize(m);
dfs(0);
dfs2(0, 1);
s = segtree(coefficient);
for(int i = 0; i < m; i++) if(A[i]) s.update(i, i);
}
int count_ways(int L, int R){
s.update(L-n, R-n);
return s.get();
}
