#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define mid ((s + e) / 2)
#define rc (2 * v + 1)
#define lc (2 * v)
const int mod = 1000002022;
int add(int a, int b){
return (a + b) % mod;
}
int mul(int a, int b){
return (1ll * a * b) % mod;
}
int n, m;
int p[MAXN];
int q[MAXN];
int dp[MAXN];
int val[MAXN];
vector<int> z;
int lazy[4 * MAXN];
vector<int> a[MAXN];
int seg[4 * MAXN][2];
void built(int v = 1, int s = 0, int e = m){
if(e - s == 1){
seg[v][z[s]] = val[s + n];
return;
}
built(lc, s, mid);
built(rc, mid, e);
seg[v][0] = add(seg[lc][0], seg[rc][0]);
seg[v][1] = add(seg[lc][1], seg[rc][1]);
}
void push(int v){
if(lazy[v] % 2)
swap(seg[v][0], seg[v][1]);
if(rc < 4 * MAXN){
lazy[rc] += lazy[v];
lazy[lc] += lazy[v];
}
lazy[v] = 0;
}
void update(int l, int r, int v = 1, int s = 0, int e = m){
push(v);
if(r <= s || e <= l) return;
if(l <= s && e <= r){
lazy[v]++;
push(v);
return;
}
update(l, r, lc, s, mid);
update(l, r, rc, mid, e);
seg[v][0] = add(seg[lc][0], seg[rc][0]);
seg[v][1] = add(seg[lc][1], seg[rc][1]);
}
void dfs(int v){
dp[v] = 1;
for(auto & u : a[v]){
dfs(u);
p[u] = dp[v];
dp[v] = mul(dp[v], dp[u]);
}
if(!a[v].empty())
dp[v] = mul(dp[v], a[v].size());
reverse(all(a[v]));
int x = 1;
for(auto & u : a[v]){
dfs(u);
q[u] = x;
x = mul(x, dp[u]);
val[u] = mul(p[u], q[u]);
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N, m = M, z = A;
for(int i = 1; i < P.size(); i++)
a[P[i]].append(i);
dfs(0);
for(int i = val[0] = 1; i < P.size(); i++)
val[i] = mul(val[i], val[P[i]]);
built();
}
int count_ways(int l, int r){
update(l - n, r - n + 1);
return seg[1][1];
}
