#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 maxn=3e5;
vector<pair<ll,ll>> tree(4*maxn+3);
vector<bool> lazy(4*maxn+3);
void intachir(ll node,ll l, ll r)
{
if(lazy[node])
{
ll cp=tree[node].first;
tree[node].first=tree[node].second;
tree[node].second=cp;
lazy[node]=false;
if(l!=r)
{
lazy[node*2+1]=true;
lazy[node*2+2]=true;
ll mid=(l+r)/2;
intachir(node*2+1,l,mid);
intachir(node*2+1,mid+1,r);
}
}
}
void build(ll node, ll l, ll r)
{
if(l==r)
{
if(a[l]==1) tree[node].first=c[l]%mod;
else tree[node].second=c[l]%mod;
return;
}
ll mid=(l+r)/2;
build(node*2+1,l,mid);
build(node*2+2,mid+1,r);
tree[node].first=(tree[node*2+1].first+tree[node*2+2].first)%mod;
tree[node].second=(tree[node*2+1].second+tree[node*2+2].second)%mod;
}
void update(ll node, ll l, ll r, ll x, ll y)
{
intachir(node,l,r);
if(max(x,l) > min(r,y))return;
if(x<=l && r<=y)
{
lazy[node]=1;
intachir(node,l,r);
return;
}
ll mid=(l+r)>>1;
update(node*2+1,l,mid,x,y);
update(node*2+2,mid+1,r,x,y);
tree[node].first=(tree[node*2+1].first+tree[node*2+2].first)%mod;
tree[node].second=(tree[node*2+1].second+tree[node*2+2].second)%mod;
}
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);
build(0,0,m-1);
}
int count_ways(int L, int R) {
update(0,0,m-1,L-n,R-n);
intachir(0,0,m-1);
return tree[0].first;
}
