#include "circuit.h"
#include <vector>
#include <cstdio>
using namespace std;
// <|°_°|>
// Jean Bombeur & M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int MOD = (1000002022);
const int MAX_NODES = (2e5);
const int LOG = (17);
const int SIZE = (1 << LOG);
struct node {
int val = 0, inv = 0, flag = 0;
};
node operator+(node a, node b) {
return {a.val + b.val >= MOD ? a.val + b.val - MOD : a.val + b.val, a.inv + b.inv >= MOD ? a.inv + b.inv - MOD : a.inv + b.inv, 0};
}
vector <int> Adj[MAX_NODES];
long long Sz[MAX_NODES];
node Tree[2 * SIZE];
int nbThresholds;
int DfsSz(int node) {
Sz[node] = Adj[node].size() + Adj[node].empty();
for (int dest : Adj[node])
Sz[node] *= DfsSz(dest), Sz[node] %= MOD;
return Sz[node];
}
void DfsSet(int node, long long value) {
if (Adj[node].empty())
Tree[SIZE + node - nbThresholds] = {0, value, 0};
vector <long long> ProdPref (1, 1);
vector <long long> ProdSuff (1, 1);
int sz = Adj[node].size();
for (int i = 0; i < sz; i ++)
{
ProdPref.push_back((ProdPref.back() * Sz[Adj[node][i]]) % MOD);
}
for (int i = sz - 1; i >= 0; i --)
{
ProdSuff.push_back((ProdSuff.back() * Sz[Adj[node][i]]) % MOD);
}
for (int i = 0; i < sz; i ++)
{
DfsSet(Adj[node][i], (((value * ProdPref[i]) % MOD) * ProdSuff[sz - i - 1]) % MOD);
}
return;
}
void Push(int node) {
Tree[node].flag = 0;
swap(Tree[node].val, Tree[node].inv);
if (node < SIZE)
Tree[2 * node].flag ^= 1, Tree[2 * node + 1].flag ^= 1;
return;
}
void Toggle(int node, int qleft, int qright, int left = 0, int right = SIZE) {
if (Tree[node].flag)
Push(node);
if (qright <= left || right <= qleft)
return;
if (qleft <= left && right <= qright)
{
Push(node);
return;
}
int mid = (left + right) >> 1;
Toggle(2 * node, qleft, qright, left, mid);
Toggle(2 * node + 1, qleft, qright, mid, right);
Tree[node] = Tree[2 * node] + Tree[2 * node + 1];
return;
}
void init(int nbNodes, int nbSources, vector <int> Parent, vector <int> States) {
nbThresholds = nbNodes;
for (int i = 1; i < nbThresholds + nbSources; i ++)
{
Adj[Parent[i]].push_back(i);
}
DfsSz(0);
DfsSet(0, 1);
for (int i = 0; i < nbSources; i ++)
{
if (States[i])
swap(Tree[i + SIZE].val, Tree[i + SIZE].inv);
}
for (int i = SIZE - 1; i; i --)
{
Tree[i] = Tree[2 * i] + Tree[2 * i + 1];
}
return;
}
int count_ways(int left, int right) {
Toggle(1, left - nbThresholds, (++ right) - nbThresholds);
return Tree[1].val;
}
