#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
const ll maxn = 100005;
vector<ll> edges[maxn];
ll sub[maxn];
ll realsub[maxn];
ll par[maxn];
ll prod[maxn];
void dfs(ll a){
if (edges[a].size()==0) sub[a] = 1;
else sub[a] = 0;
prod[a] = 1;
for (auto&i : edges[a]){
dfs(i);
sub[a] += sub[i];
prod[a] *= sub[i];
prod[a] %= 1000002022;
}
}
ll cache[maxn];
ll dp(ll a){
if (cache[a] != -1) return cache[a];
if (a==0) return 1;
cache[a] = dp(par[a]);
for (auto&i : edges[par[a]]){
if (i != a) cache[a] *= sub[i];
cache[a] %= 1000002022;
}
return cache[a]% 1000002022;
}
ll states[maxn];
ll ans = 0;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
FOR(i,0,maxn) cache[i] = -1;
par[0] = -1;
FOR(i,1,N+M){
edges[P[i]].push_back(i);
par[i] = P[i];
}
dfs(0);
FOR(i,0,M){
states[N+i] = A[i];
if (A[i]==1) ans += dp(N+i);
ans %= 1000002022;
}
}
int count_ways(int L, int R) {
FOR(i,L,R+1){
if (states[i]==1){
states[i] = 0;
ans -= dp(i);
}else{
states[i] = 1;
ans += dp(i);
}
ans %= 1000002022;
}
return (ans+1000002022)%1000002022;
}
