#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1'000'002'022;
vector<int> adj[800800];
int n, m, a[800800];
struct Seg1{
ll tree[800800], sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = adj[i-sz].size();
for (int i=sz-1;i;i--) tree[i] = tree[i<<1] * tree[i<<1|1] % MOD;
}
void update(int p, int x){
for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = tree[p] * tree[p^1] % MOD;
}
}tree1;
struct Seg2{
pair<ll, ll> tree[800800];
int lazy[800800];
pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){return {(x.first + y.first)%MOD, (x.second + y.second)%MOD};}
void init(int i, int l, int r){
lazy[i] = 0;
if (l==r) {tree[i] = {0, a[l]}; return;}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = combine(tree[i<<1], tree[i<<1|1]);
}
void propagate(int i, int l, int r){
if (!lazy[i]) return;
swap(tree[i].first, tree[i].second);
if (l!=r){
lazy[i<<1] ^= 1;
lazy[i<<1|1] ^= 1;
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] ^= 1;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e); update(i<<1|1, m+1, r, s, e);
tree[i] = combine(tree[i<<1], tree[i<<1|1]);
}
}tree2;
void dfs(int s){
if (s<=n) tree1.update(s, 1);
else a[s-n] = tree1.tree[1];
for (auto &v:adj[s]) dfs(v);
if (s<=n) tree1.update(s, adj[s].size());
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
adj[0].push_back(0);
n = N, m = M;
for (int i=1;i<n+m;i++){
adj[P[i]+1].push_back(i+1);
}
tree1.init(n+1);
dfs(1);
tree2.init(1, 1, m);
for (int i=0;i<m;i++) if (A[i]) tree2.update(1, 1, m, i+1, i+1);
}
int count_ways(int L, int R) {
tree2.update(1, 1, m, L-n+1, R-n+1);
return tree2.tree[1].first;
}
