#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int mod = 1000002022;
void add(int& a, int b){
if((a += b) >= mod){
a -= mod;
}
}
void sub(int& a, int b){
if((a -= b) < 0){
a += mod;
}
}
int n, m, parent[lim], a[lim];
vector<int>g[lim];
namespace sub1237{
const int lim = 1e4 + 5;
int ans = 0, f[lim], coef[lim];
bitset<lim>vis;
void init(){
for(int i = n; i < n + m; i++){
vector<int>path;
int u = i;
vis.reset();
while(u != -1){
vis.set(u);
u = parent[u];
}
f[i] = 1;
for(int j = 0; j < n; j++){
if(!vis.test(j)){
f[i] = 1LL * f[i] * g[j].size() % mod;
}
}
if(a[i] == 1){
add(ans, f[i]);
}
}
}
int query(int L, int R){
for(int i = L; i <= R; i++){
if((a[i] ^= 1) == 0){
sub(ans, f[i]);
}
else{
add(ans, f[i]);
}
}
return ans;
}
}
namespace sub8{
int f[lim], st[lim << 2];
bitset<lim << 2>lazy;
void fix(int id){
st[id] = (st[id << 1] + st[id << 1 | 1]) % mod;
}
void flip(int id, int l, int r){
lazy.flip(id);
st[id] = ((f[r] - f[l - 1] + mod) % mod - st[id] + mod) % mod;
}
void build(int id, int l, int r){
if(l == r){
st[id] = (a[l] == 0 ? 0 : (f[l] - f[l - 1] + mod) % mod);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
fix(id);
}
void push_down(int id, int l, int r, int m){
if(lazy.test(id)){
lazy.reset(id);
flip(id << 1, l, m);
flip(id << 1 | 1, m + 1, r);
}
}
void update(int id, int l, int r, int u, int v){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
flip(id, l, r);
return;
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
update(id << 1, l, m, u, v);
update(id << 1 | 1, m + 1, r, u, v);
fix(id);
}
void init(){
function<void(int)>dfs_1, dfs_2, dfs_3;
dfs_1 = [&] (int s){
f[s] = g[s].size();
for(int& d : g[s]){
if(!g[d].empty()){
dfs_1(d);
f[s] = 1LL * f[s] * f[d] % mod;
}
else{
f[d] = 1;
}
}
};
dfs_1(0);
dfs_2 = [&] (int s){
vector<int>suffix(g[s].size() + 2);
suffix[g[s].size() + 1] = 1;
for(int i = g[s].size(); i > 0; i--){
int d = g[s][i - 1];
suffix[i] = 1LL * suffix[i + 1] * f[d] % mod;
}
for(int i = 1, prefix = 1; i <= g[s].size(); i++){
int d = g[s][i - 1], temp = f[d];
f[d] = 1LL * prefix * suffix[i + 1] % mod;
dfs_2(d);
prefix = 1LL * prefix * temp % mod;
}
};
dfs_2(0);
f[0] = 1;
dfs_3 = [&] (int s){
for(int& d : g[s]){
f[d] = 1LL * f[d] * f[s] % mod;
dfs_3(d);
}
};
dfs_3(0);
f[n - 1] = 0;
for(int i = n; i < n + m; i++){
add(f[i], f[i - 1]);
}
lazy.reset();
build(1, n, n + m - 1);
}
int query(int L, int R){
update(1, n, n + m - 1, L, R);
return st[1];
}
}
void init(int N, int M, vector<int>P, vector<int>A){
n = N;
m = M;
parent[0] = -1;
for(int i = 1; i < n + m; i++){
g[parent[i] = P[i]].emplace_back(i);
}
for(int i = 0; i < m; i++){
a[i + n] = A[i];
}
if(max(n, m) <= 5000 && false){
sub1237::init();
}
else{
sub8::init();
}
}
int count_ways(int L, int R){
if(max(n, m) <= 5000 && false){
return sub1237::query(L, R);
}
return sub8::query(L, R);
}
