#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define pb push_back
#define ln '\n'
const int Mod = 1000002022;
vector <int> a;
vector <vector<int>> adj;
vector <int> dp;
int n, m;
struct SegTree{
vector <ar<int,2>> T;
vector <int> lazy;
int n;
SegTree() {}
void modify(int _n, vector <int> val, vector <int> state){
n = _n;
T.resize(n * 4 + 5);
lazy.resize(n * 4 + 5);
auto build = [&](auto build, int v, int l, int r) -> void{
if ( l == r ){
T[v][state[l]] = val[l];
return;
}
int m = (l + r) / 2;
build(build, v * 2, l, m);
build(build, v * 2 + 1, m + 1, r);
for ( auto j: {0, 1} ){
T[v][j] = (T[v * 2][j] + T[v * 2 + 1][j]) % Mod;
}
};
build(build, 1, 0, n - 1);
}
void push(int v, int l, int r){
if ( !lazy[v] ) return;
if ( l != r ){
lazy[v * 2] ^= lazy[v];
lazy[v * 2 + 1] ^= lazy[v];
}
swap(T[v][1], T[v][0]);
lazy[v] = 0;
}
void upd(int v, int l, int r, int tl, int tr){
push(v, l, r);
if ( l > tr or r < tl ) return;
if ( tl <= l && tr >= r ){
lazy[v] = 1;
push(v, l, r);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, tl, tr);
upd(v * 2 + 1, m + 1, r, tl, tr);
for ( auto j: {0, 1} ){
T[v][j] = (T[v * 2][j] + T[v * 2 + 1][j]) % Mod;
}
}
void upd(int l, int r){
upd(1, 0, m - 1, l, r);
}
int qry(){
push(1, 0, m - 1);
return T[1][1];
}
};
template <class F, class S>
void add(F &x, const S &y){
x = (x + 0LL + y) % Mod;
if ( x < 0 ) x += Mod;
}
SegTree seg;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
a = A, n = N, m = M;
adj.resize(n + m);
for ( int i = 1; i < n + m; i++ ){
adj[P[i]].pb(i);
}
vector <int> s(n + m);
auto trav = [&](auto trav, int u) -> void{
if ( u >= n ){
s[u] = 1; return;
}
s[u] = adj[u].size();
for ( auto &v: adj[u] ){
trav(trav, v);
s[u] = s[u] * 1LL * s[v] % Mod;
}
};
trav(trav, 0);
dp.resize(m);
auto dfs = [&](auto dfs, int u, int cnt) -> void{
if ( u >= n ){
dp[u - n] = cnt;
return;
}
int sz = adj[u].size();
vector <int> child, vl;
for ( auto &v: adj[u] ){
child.pb(v); vl.pb(s[v]);
}
vector <int> pf(sz + 1, 1), sf(sz + 2, 1);
for ( int i = 0; i < sz; i++ ){
pf[i + 1] = pf[i] * 1LL * vl[i] % Mod;
}
for ( int i = sz; i > 0; i-- ){
sf[i] = sf[i + 1] * 1LL * vl[i - 1] % Mod;
}
for ( int i = 0; i < sz; i++ ){
int nxt = cnt * 1LL * pf[i] % Mod * sf[i + 2] % Mod;
dfs(dfs, child[i], nxt);
}
};
dfs(dfs, 0, 1);
seg.modify(m, dp, a);
}
int count_ways(int L, int R) {
L -= n, R -= n;
seg.upd(L, R);
return seg.qry();
}
