#include "circuit.h"
#include <vector>
#include <functional>
#include <cmath>
#include <iostream>
using ll = long long;
using namespace std;
//모든 인덱스에 1씩 더하기
int par[200005];
ll tot[200005];
ll dp[200005];
vector<int> g[200005];
vector<int> prf[200005], suf[200005];
const ll mod = 1'000'002'022;
ll ans = 0;
namespace {
int N, M;
}
//A[i]: N+1+i의 상태
struct sumseg
{
vector<ll> tree, lazy;
void setup(int n)
{
int sz = 1 << ((int)ceil(log2(n+1))+1);
tree.resize(sz); lazy.resize(sz, 1);
}
int init(int s, int e, int node, vector<ll> &arr)
{
if (s == e) return tree[node] = arr[s];
else return tree[node] = (init(s, (s+e)/2, 2*node, arr) + init((s+e)/2+1, e, 2*node+1, arr)) % mod;
}
void propagate(int s, int e, int node)
{
tree[node] *= lazy[node];
if (s != e) {
lazy[2*node] *= lazy[node];
lazy[2*node+1] *= lazy[node];
}
lazy[node] = 1;
}
void upd(int s, int e, int node, int l, int r)
{
propagate(s, e, node);
if (e < l || r < s) return;
if (l <= s && e <= r) {
lazy[node] *= -1;
propagate(s, e, node);
return;
}
upd(s, (s+e)/2, 2*node, l, r);
upd((s+e)/2+1, e, 2*node+1, l, r);
tree[node] = (tree[2*node] + tree[2*node+1]) % mod;
}
int query(int s, int e, int node, int l, int r)
{
propagate(s, e, node);
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[node];
return (query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r)) % mod;
}
}seg;
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
::N = N;
::M = M;
seg.setup(M);
par[1] = 0;
for (int i = 1; i < N + M; i++) {
par[i+1] = P[i] + 1;
}
for (int i = 2; i <= N + M; i++) g[par[i]].push_back(i);
function<void(int)> dfs = [&](int v)
{
if (v <= N) {
tot[v] = g[v].size();
for (int j:g[v]) {
dfs(j);
tot[v] = tot[v] * tot[j] % mod;
}
}
else {
tot[v] = 1;
}
};
dfs(1);
function<void(int)> dfs2 = [&](int v)
{
if (v > N) return;
for (int j:g[v]) dfs2(j);
prf[v].resize(g[v].size());
suf[v].resize(g[v].size());
prf[v][0] = tot[g[v][0]];
suf[v].back() = tot[g[v].back()];
for (int i = 1; i < (int)prf[v].size(); i++) {
prf[v][i] = prf[v][i-1] * tot[g[v][i]] % mod;
}
for (int i = (int)suf[v].size() - 2; i >= 0; i--) {
suf[v][i] = suf[v][i+1] * tot[g[v][i]] % mod;
}
};
dfs2(1);
dp[1] = 1;
function<void(int)> dfs3 = [&](int v)
{
for (int j = 0; j < (int)g[v].size(); j++) {
ll mul = 1;
if (j >= 1) mul = mul * prf[v][j-1] % mod;
if (j <= (int)g[v].size() - 2) mul = mul * suf[v][j+1] % mod;
dp[g[v][j]] = dp[v] * mul % mod;
dfs3(g[v][j]);
}
};
dfs3(1);
for (int i = N + 1; i <= N + M; i++) ans = (ans + A[i-N-1] * dp[i]) % mod;
vector<ll> st(M);
for (int i = N + 1; i <= N + M; i++) {
st[i-N-1] = A[i-N-1] == 1 ? -dp[i] : dp[i];
}
seg.init(0, M-1, 1, st);
}
int count_ways(int L, int R) {
int l = L - N, r = R - N;
ans += seg.query(0, M-1, 1, l, r);
seg.upd(0, M-1, 1, l, r);
ans = (ans % mod + mod) % mod;
return ans;
}
