#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
#define ll long long
using namespace std;
const ll mod = 1000002022;
const int N = 300010;
vector <int> g[N];
ll tot[N], c[N];
int pai[N];
vector <int> start;
int n;
struct Segtree{
struct Node{
ll val, soma;
int lazy;
} tree[4*N], nulo;
Node join(Node a, Node b){
Node res;
res.val = a.val+b.val;
res.val %= mod;
res.soma = a.soma+b.soma;
res.soma %= mod;
res.lazy = 0;
return res;
}
void unlazy(int node, int l, int r){
if(!tree[node].lazy) return;
tree[node].val = tree[node].soma - tree[node].val;
tree[node].val %= mod;
tree[node].val += mod;
tree[node].val %= mod;
if(l != r){
tree[2*node].lazy ^= tree[node].lazy;
tree[2*node+1].lazy ^= tree[node].lazy;
}
tree[node].lazy = 0;
}
void build(int node, int l, int r){
if(node == 1){
nulo.val = nulo.soma = 0;
nulo.lazy = 0;
}
tree[node].lazy = 0;
if(l == r){
tree[node].soma = c[l+n-1];
tree[node].val = (start[l-1] == 1 ? tree[node].soma : 0);
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
tree[node].lazy ^= 1;
unlazy(node, tl, tr);
return;
}
int mid =(tl+tr)/2;
update(2*node, l, r, tl, mid);
update(2*node+1, l, r, mid+1, tr);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
Node query(int node, int l, int r, int tl, int tr){
unlazy(node, tl ,tr);
if(l > tr or tl > r) return nulo;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
void dfs(int v, int p){
if(g[v].size() == 0){
pai[v] = p;
tot[v] = 1;
return;
}
pai[v] = p;
tot[v] = 1;
for(auto x : g[v]){
dfs(x, v);
tot[v] *= tot[x];
tot[v] %= mod;
}
tot[v] *= (ll) g[v].size();
tot[v] %= mod;
return;
}
ll pref[N], suf[N];
void dfs2(int v, int p){
// c[v] = mul(dividir(tot[p], mul(g[p].size(), tot[v])), c[p]);
pref[0] = 1;
suf[g[v].size()+1] = 1;
for(int i = 1;i <= g[v].size();i++){
int x = g[v][i-1];
pref[i] = (pref[i-1]*tot[x]) % mod;
}
for(int i = g[v].size();i > 0;i--){
int x = g[v][i-1];
suf[i] = (suf[i+1]*tot[x]) % mod;
}
for(int i = 1;i <= g[v].size();i++){
int x = g[v][i-1];
c[x] = (pref[i-1]*suf[i+1])% mod;
c[x] *= c[v];
c[x] %= mod;
}
for(auto x : g[v]){
dfs2(x, v);
}
return;
}
int m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
start = A;
m = M;
n = N;
for(int i = 1;i < P.size();i++){
g[P[i]].push_back(i);
}
dfs(0, 0);
c[0] = 1;
dfs2(0, 0);
/*for(int i = 0;i < n+m;i++){
cout << tot[i] << ' ' << c[i] << '\n';
}
cout << '\n';*/
seg.build(1, 1, M);
}
int count_ways(int l, int r) {
l -= n-1;
r -= n-1;
seg.update(1, l, r, 1, m);
return seg.query(1, 1, m, 1, m).val;
}
