#include "circuit.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1'000'002'022, LIM = 1e6+1, inf = 2e9;
int add(int x,int y) {
if ((x + y) >= MOD) return x + y - MOD;
return x + y;
}
int mult(int x,int y) {
return (1LL * x * y) % MOD;
}
int expo(int x,int y) {
if (!y) return 1;
int e = expo(x,y/2);
e = mult(e,e);
if (y&1) e= mult(e,x);
return e;
}
vi edges[LIM];
vector<pii> dp(LIM);
vi useful(LIM,0);
vector<int32_t> a;
int nn;
pii dfs(int node) {
if (!useful[node]) return dp[node];
if (node >= nn) {
return dp[node] = {a[node-nn],1-a[node-nn]};
}
int sz = edges[node].size();
vector<vi> dp2(sz+1,vi(sz+1,0));
dp2[0][0] = 1;
int cur = 0;
for (auto it : edges[node]) {
pii r = dfs(it);
for (int j = 0;j<=cur;j++) {
dp2[cur+1][j] = add(dp2[cur+1][j],mult(dp2[cur][j],r.ss));
if (j<sz) dp2[cur+1][j+1] = add(dp2[cur+1][j+1],mult(dp2[cur][j],r.ff));
}
cur++;
}
int posible = 0,imposible = 0;
for (int j = 0;j<=sz;j++) posible = add(posible,mult(dp2[sz][j],j));
for (int j = 0;j<=sz;j++) imposible = add(imposible,mult(dp2[sz][j],sz-j));
return dp[node] = {posible,imposible};
}
vector<int32_t> par;
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
a = A;
nn = N;
par = P;
for (int i=1;i<N+M;i++) edges[P[i]].push_back(i);
useful.assign(LIM,1);
dfs(0);
useful.assign(LIM,0);
}
int32_t count_ways(int32_t L, int32_t R) {
for (int i = L-nn;i<=R-nn;i++) a[i]^=1;
for (int ii=L;ii<=R;ii++) {
int cur = ii;
while (cur != -1) {
useful[cur] = 1;
cur = par[cur];
}
}
dfs(0);
for (int ii=L;ii<=R;ii++) {
int cur = ii;
while (cur != -1) {
useful[cur] = 0;
cur = par[cur];
}
}
return dp[0].ff;
}
