#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const string asafaciunstringsus = R""""(
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
)"""";
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int st, int dr)
{
uniform_int_distribution<int> dist(st, dr);
return dist(rng);
}
template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
const int mod = 1000002022;
struct Mint
{
int val;
Mint(int x = 0)
{
val = (x % mod + mod) % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint operator*(Mint oth)
{
return 1ll * val * oth.val;
}
void operator+=(Mint oth)
{
val = (*this + oth).val;
}
void operator-=(Mint oth)
{
val = (*this - oth).val;
}
void operator*=(Mint oth)
{
val = (*this * oth).val;
}
};
Mint powmod(int a, int b)
{
if (b == 0)
{
return 1;
}
if (b % 2 == 1)
{
return powmod(a, b - 1) * a;
}
Mint p = powmod(a, b / 2);
return p * p;
}
/*
.___ __ __ .__
____ ____ __| _/____ _______/ |______ ________/ |_ ______ | |__ ___________ ____
_/ ___\/ _ \ / __ |/ __ \ / ___/\ __\__ \\_ __ \ __\/ ___/ | | \_/ __ \_ __ \_/ __ \
\ \__( <_> ) /_/ \ ___/ \___ \ | | / __ \| | \/| | \___ \ | Y \ ___/| | \/\ ___/
\___ >____/\____ |\___ > /____ > |__| (____ /__| |__| /____ > |___| /\___ >__| \___ >
\/ \/ \/ \/ \/ \/ \/ \/ \/
*/
struct aint
{
vector<Mint> a;
vector<Mint> sp;
vector<int> lazy;
aint() {}
aint(int n, vector<Mint> coef)
{
a.resize(4 * n);
lazy.resize(4 * n);
sp.push_back(0);
for (int i = 0; i < n; ++i)
{
sp.push_back(sp.back() + coef[i]);
}
}
void prop(int node, int left, int right)
{
if (lazy[node])
{
a[node] = sp[right] - sp[left - 1] - a[node];
if (left != right)
{
lazy[2 * node] ^= 1;
lazy[2 * node + 1] ^= 1;
}
lazy[node] = 0;
}
}
void update(int node, int left, int right, int st, int dr)
{
prop(node, left, right);
if (right < st || left > dr)
{
return;
}
if (st <= left && dr >= right)
{
lazy[node] ^= 1;
prop(node, left, right);
return;
}
int mid = (left + right) / 2;
update(2 * node, left, mid, st, dr);
update(2 * node + 1, mid + 1, right, st, dr);
a[node] = a[2 * node] + a[2 * node + 1];
}
};
int n, m;
aint lesgo;
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n = N + M;
m = M;
vector<Mint> coef(m);
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i)
{
g[P[i]].push_back(i);
}
vector<Mint> prod(n);
function<void(int)> dfs_prod = [&](int node)
{
if (g[node].empty())
{
prod[node] = 1;
return;
}
prod[node] = (int)g[node].size();
for (auto it : g[node])
{
dfs_prod(it);
prod[node] *= prod[it];
}
};
dfs_prod(0);
vector<Mint> ans(n, 1);
function<void(int)> dfs = [&](int node)
{
if (g[node].empty())
{
coef[node - N] = ans[node];
return;
}
vector<Mint> children;
for (auto it : g[node])
{
children.push_back(prod[it]);
}
vector<Mint> prefprod(children.size()), sufprod(children.size());
prefprod[0] = children[0];
sufprod.back() = children.back();
for (int i = 1; i < children.size(); ++i)
{
prefprod[i] = prefprod[i - 1] * children[i];
}
for (int i = children.size() - 2; i >= 0; --i)
{
sufprod[i] = sufprod[i + 1] * children[i];
}
for (int i = 0; i < children.size(); ++i)
{
int it = g[node][i];
ans[it] = ans[node];
if (i != 0)
{
ans[it] *= prefprod[i - 1];
}
if (i != children.size() - 1)
{
ans[it] *= sufprod[i + 1];
}
dfs(it);
}
};
dfs(0);
lesgo = aint(m, coef);
for (int i = 0; i < m; ++i)
{
if (A[i])
{
lesgo.update(1, 1, m, i + 1, i + 1);
}
}
}
int count_ways(int L, int R)
{
L -= n - m - 1;
R -= n - m - 1;
lesgo.update(1, 1, m, L, R);
return lesgo.a[1].val;
}
/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before
Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/
