#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 2022;
struct SegTree {
struct info {
int sumTot, sumActive;
info operator + ( info &x ) {
return { (sumTot + x.sumTot) % MOD, (sumActive + x.sumActive) % MOD };
}
};
int lst, rst;
vector<info> aint;
vector<int> lazy;
void init( int v, int l, int r, int val[] ) {
lazy[v] = 0;
if ( l == r ) {
aint[v] = { val[0], val[0] };
return;
}
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid, val );
init( v * 2 + 2, mid + 1, r, val + mid + 1 - l );
aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
}
void init( int l, int r, int val[] ) {
lst = l;
rst = r;
aint.resize( 4 * (r - l + 1) );
lazy.resize( 4 * (r - l + 1) );
init( 0, lst, rst, val );
}
void propag( int v, int l, int r ) {
if ( !lazy[v] )
return;
aint[v].sumActive = (aint[v].sumTot - aint[v].sumActive + MOD) % MOD;
if ( l != r ) {
lazy[v * 2 + 1] ^= 1;
lazy[v * 2 + 2] ^= 1;
}
lazy[v] = 0;
}
void update( int v, int l, int r, int lu, int ru ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] = 1;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru );
update( v * 2 + 2, mid + 1, r, lu, ru );
aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
}
void update( int l, int r ) {
update( 0, lst, rst, l, r );
}
int queryActive() {
return aint[0].sumActive;
}
} aint;
const int MAX_N = 2e5;
int value[MAX_N], dpTot[MAX_N];
vector<int> adj[MAX_N], prefix[MAX_N], suffix[MAX_N];
int n, m;
void dfsDpTot( int u ) {
for ( int v: adj[u] )
dfsDpTot( v );
dpTot[u] = 1;
if ( adj[u].size() == 0 )
return;
for ( int v: adj[u] )
dpTot[u] = (long long)dpTot[u] * dpTot[v] % MOD;
dpTot[u] = (long long)dpTot[u] * adj[u].size() % MOD;
}
void dfsCalcValues( int u, int val ) {
if ( adj[u].size() == 0 ) {
value[u] = val;
return;
}
prefix[u].resize( adj[u].size() + 1 );
suffix[u].resize( adj[u].size() + 1 );
prefix[u][0] = 1;
for ( int i = 0; i < adj[u].size(); i++ ) {
int v = adj[u][i];
prefix[u][i + 1] = (long long)prefix[u][i] * dpTot[v] % MOD;
}
suffix[u][adj[u].size()] = 1;
for ( int i = adj[u].size() - 1; i >= 0; i-- ) {
int v = adj[u][i];
suffix[u][i] = (long long)suffix[u][i + 1] * dpTot[v] % MOD;
}
for ( int i = 0; i < adj[u].size(); i++ ){
int v = adj[u][i];
dfsCalcValues( v, (long long)val * prefix[u][i] % MOD * suffix[u][i + 1] % MOD );
}
}
void init( int N, int M, vector<int> P, vector<int> A ) {
n = N + M, m = M;
for ( int v = 1; v < n; v++ )
adj[P[v]].push_back( v );
dfsDpTot( 0 );
dfsCalcValues( 0, 1 );
aint.init( n - m, n - 1, value + n - m );
for ( int v = 0; v < m; v++ ) {
if ( A[v] == 0 )
aint.update( v + n - m, v + n - m );
}
}
int count_ways( int l, int r ) {
aint.update( l, r );
return aint.queryActive();
}
