#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
const int mod = 1000002022;
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define add(x, y) (x + y >= mod? x+y-mod: x+y)
#define sub(x, y) (x - y < 0? x-y+mod: x-y)
const int maxn = 1e5 + 10;
int n, m, p[maxn << 1], a[maxn], dp[maxn], val[maxn], cnt[maxn][2], phi = 1 * 222 * 2242156;
pii seg[maxn << 2];
bool lazy[maxn << 2];
vector<int> g[maxn];
int pw(int a, int b){
// debug(a, b);
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
// debug(res);
return res;
}
pair<int,pii> dfs(int v){
if (v >= n){
val[v] = 1;
return {1, {0, 0}};
}
int x = g[v].size();
while(x % 2 == 0){
cnt[v][0]++;
x /= 2;
}
while(x % 223 == 0){
cnt[v][1]++;
x /= 223;
}
val[v] = x;
pair<int,pii> res = {val[v], {cnt[v][0], cnt[v][1]}};
for (auto u: g[v]){
pair<int,pii> tmp = dfs(u);
res.F = 1ll * res.F * tmp.F % mod;
res.S.F += tmp.S.F;
res.S.S += tmp.S.S;
}
return res;
}
void solve(int v, pair<int,pii> tmp){
//debug(v);
if (v >= n){
dp[v-n] = 1ll * tmp.F * pw(2, tmp.S.F) % mod * pw(223, tmp.S.S) % mod;
// debug(v, dp[v-n], tmp.F, tmp.S.F, tmp.S.S);
return;
}
tmp.F = 1ll * tmp.F * pw(val[v], phi-1) % mod;
tmp.S.F -= cnt[v][0];
tmp.S.S -= cnt[v][1];
for (auto u: g[v]){
solve(u, tmp);
}
}
pii operator +(pii a, pii b){
return MP(add(a.F, b.F), add(a.S, b.S));
}
void shift(int v, int l, int r);
void build(int v, int l, int r){
if (l + 1 == r){
seg[v] = {dp[l], 0};
if (a[l] == 0) swap(seg[v].F, seg[v].S);
return;
}
int mid = (l + r) >> 1;
build(v << 1, l, mid);
build(v << 1 | 1, mid, r);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
void change(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
swap(seg[v].F, seg[v].S);
lazy[v] = !lazy[v];
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
change(v << 1, l, mid, ql, qr);
change(v << 1 | 1, mid, r, ql, qr);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
void shift(int v, int l, int r){
if (!lazy[v]) return;
int mid = (l + r) >> 1;
change(v << 1, l, mid, l, mid);
change(v << 1 | 1, mid, r, mid, r);
lazy[v] = false;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
for (int i = 1; i < n+m; i++){
p[i] = P[i];
g[p[i]].push_back(i);
}
for (int i = 0; i < m; i++) a[i] = A[i];
// debug(1);
pair<int,pii> tmp = dfs(0);
// debug(tmp.F, tmp.S.F, tmp.S.S);
// debug(2);
solve(0, tmp);
// debug(3);
build(1, 0, m);
}
int count_ways(int L, int R) {
L -= n;
R -= n;
change(1, 0, m, L, R+1);
return seg[1].F;
}
