#include "circuit.h"
#include<bits/stdc++.h>
#define ll long long
#define mod 1000002022
#define dbg(x) cerr<<#x << ' ' << x << endl;
using namespace std;
#include <vector>
vector<vector<ll>> adj;
ll n,m;
vector<ll> a;
vector<ll> c;
map<pair<ll,ll>, ll> w;
ll dfs(ll node, ll par)
{
if(adj[node].size()==1 && node!=par) return 1;
vector<ll> v(adj[node].size());
vector<ll> p(adj[node].size());
vector<ll> s(adj[node].size());
ll d=adj[node].size()-1;
if(node==par)d++;
for (int i=0;i<adj[node].size();i++)
{
if(adj[node][i]==par)
{
v[i]=1;
p[i]=v[i];
if(i>0)p[i]*=p[i-1];
continue;
}
v[i]=dfs(adj[node][i],node);
p[i]=v[i];
if(i>0)
{
p[i]*=p[i-1];
p[i]%=mod;
}
}
for (int i=adj[node].size()-1;i>=0;i--)
{
s[i]=v[i];
if(i!=adj[node].size()-1)
{
s[i]*=s[i+1];
s[i]%=mod;
}
}
for (int i=0;i<adj[node].size();i++)
{
if(adj[node][i]==par)continue;
ll lft=1;
ll r=1;
if(i>0)lft=p[i-1];
if(i<adj[node].size()-1)r=s[i+1];
ll val=lft*r%mod;
w[{node,adj[node][i]}]=val;
w[{adj[node][i],node}]=val;
}
ll pr=p.back()*d%mod;
return pr;
}
void calculate(ll node, ll par, ll pr)
{
if(adj[node].size()==1 && node!=par)
{
c[node-n]=pr;
return;
}
for (auto &&e : adj[node])
{
if(e==par)continue;
calculate(e,node,pr*w[{node,e}]%mod);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
m=M;
c.assign(m,1);
adj.resize(n+m);
for (int i=0;i<m;i++)a.push_back(A[i]);
for (int i=1;i<n+m;i++)
{
adj[i].push_back(P[i]);
adj[P[i]].push_back(i);
}
dfs(0,0);
calculate(0,0,1);
}
int count_ways(int L, int R) {
ll ans=0;
for (int i=L;i<=R;i++)
{
a[i-n]^=1;
}
for (int i=0;i<m;i++)
{
ans+=a[i]*c[i];
ans%=mod;
}
return ans;
}
