#include "circuit.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
vector<int> a,p;
ll siz = 1;
pair<ll,ll> seg[2*200005];
ll n;
ll mod = 1000002022;
ll op[2*200005];
void build(ll x = 0, ll lx = 0, ll rx = siz)
{
if(rx-lx==1)
{
seg[x].F = a[lx];
seg[x].S = !a[lx];
return;
}
ll mid = (lx+rx)/2;
build(2*x+1,lx,mid);
build(2*x+2,mid,rx);
seg[x].F = ((2*seg[2*x+1].F*seg[2*x+2].F)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
seg[x].S = ((2*seg[2*x+1].S*seg[2*x+2].S)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
}
void upd(ll l , ll r, ll x = 0, ll lx = 0, ll rx = siz)
{
if(lx>=r||rx<=l) return;
if(lx>=l&&rx<=r)
{
swap(seg[x].F, seg[x].S);
op[x] ^= 1;
return;
}
ll mid = (lx+rx)/2;
upd(l,r,2*x+1,lx,mid);
upd(l,r,2*x+2,mid,rx);
seg[x].F = ((2*seg[2*x+1].F*seg[2*x+2].F)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
seg[x].S = ((2*seg[2*x+1].S*seg[2*x+2].S)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
// if(op[x]) swap(seg[x].F, seg[x].S);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
p = P;
siz = M;
a = A;
n = N;
build();
}
int count_ways(int L, int R) {
//upd(L,R+1);
ll x = L+n;
swap(seg[x].F,seg[x].S);
x = p[x];
while(x!=-1)
{
seg[x].F = ((2*seg[2*x+1].F*seg[2*x+2].F)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
seg[x].S = ((2*seg[2*x+1].S*seg[2*x+2].S)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
x = p[x];
}
return seg[0].F;
}
