#include "circuit.h"
#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#else
#define D(x) ;
#endif
using namespace std;
using ll = long long;
int n, m;
vector<int> ps;
vector<int> as;
vector<vector<int>> al;
vector<int> tss;
vector<int> tcs;
vector<int> td1;
vector<int> td2;
vector<int> ts1;
vector<int> ts2;
vector<int> mults;
int ms = 1;
int mis[400000];
int miv[400000];
bool ml[400000];
constexpr int m2 = 2242157;
constexpr int mod = 2*223*m2;
constexpr int ord = 222*2242156;
int bexp(ll b, ll e) {
if(e < 0) e += ord;
ll r = 1;
while(e > 0) {
if(e&1) {
r *= b;
r %= mod;
}
e /= 2;
b *= b;
b %= mod;
}
return r;
}
void iwalk(int v) {
tcs[v] = 1;
tss[v] = 1;
int c = al[v].size()-1;
if(ps[v] == -1) c += 1;
if(c == 0) return;
while(c % 2 == 0) {
c /= 2;
ts1[v] += 1;
}
while(c % 223 == 0) {
c /= 223;
ts2[v] += 1;
}
tss[v] = c;
D(v)
D(tss[v])
for(auto a : al[v]) {
if(a == ps[v]) continue;
iwalk(a);
tcs[v] = (1ll*tcs[v]*tss[a]) % mod;
td1[v] += ts1[a];
td2[v] += ts2[a];
}
tss[v] = (1ll*tcs[v]*tss[v]) % mod;
ts1[v] += td1[v];
ts2[v] += td2[v];
}
void mwalk(int v, int ml, int d1, int d2) {
if(v >= n) {
mults[v-n] = ml;
mults[v-n] = (1ll*bexp(2, d1)*mults[v-n]) % mod;
mults[v-n] = (1ll*bexp(223, d2)*mults[v-n]) % mod;
}
for(auto a : al[v]) {
if(a == ps[v]) continue;
ll nm = 1ll*ml*tcs[v];
nm %= mod;
nm *= bexp(tss[a], -1);
nm %= mod;
mwalk(a, nm, d1+td1[v]-ts1[a], d2+td2[v]-ts2[a]);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
ps = std::move(P);
as = std::move(A);
al.resize(N+M);
mults.resize(M);
tcs.resize(N+M);
td1.resize(N+M);
td2.resize(N+M);
tss.resize(N+M);
ts1.resize(N+M);
ts2.resize(N+M);
for(int i = 1; i < n+m; ++i) {
al[i].push_back(ps[i]);
al[ps[i]].push_back(i);
}
iwalk(0);
mwalk(0, 1, 0, 0);
if(0) {
for(int i = 0; i < n+m; ++i) {
cerr << tcs[i] << ' ';
}
cerr << '\n';
for(int i = 0; i < m; ++i) {
cerr << mults[i] << ' ';
}
cerr << '\n';
}
ms = 1;
while(ms < m) ms *= 2;
for(int i = 0; i < m; ++i) {
mis[ms+i] = mults[i];
}
for(int i = ms-1; i > 0; --i) {
mis[i] = (mis[2*i] + mis[2*i+1]) % mod;
}
for(int i = 0; i < m; ++i) {
miv[ms+i] = mis[ms+i]*as[i];
}
for(int i = ms-1; i > 0; --i) {
miv[i] = (miv[2*i] + miv[2*i+1]) % mod;
}
}
void flip(int l, int r, int ul, int ur, int u) {
if(ml[u]) {
miv[u] = mis[u] - miv[u];
miv[u] %= mod;
if(u < ms) {
ml[2*u] ^= 1;
ml[2*u+1] ^= 1;
}
ml[u] = false;
}
if(l >= r) return;
if(r <= ul) return;
if(ur <= l) return;
if(l <= ul && ur <= r) {
miv[u] = mis[u] - miv[u];
miv[u] %= mod;
if(u < ms) {
ml[2*u] ^= 1;
ml[2*u+1] ^= 1;
}
return;
}
int um = (ul+ur)/2;
flip(l, r, ul, um, 2*u);
flip(l, r, um, ur, 2*u+1);
miv[u] = (miv[2*u] + miv[2*u+1]) % mod;
}
int count_ways(int L, int R) {
L -= n;
R -= n;
++R;
flip(L, R, 0, ms, 1);
int res = miv[1];
while(res < 0) res += mod;
return res;
}
