#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022ll;
int N, M;
vector<int> A;
vector<vector<int>> adj;
vector<pair<ll, ll>> nodes;
void DFS(int index)
{
if (index >= N)
{
if (A[index - N])
nodes[index] = {1, 0};
else
nodes[index] = {0, 1};
return;
}
for (auto node : adj[index])
{
DFS(node);
}
const auto l = nodes[adj[index][0]];
const auto r = nodes[adj[index][1]];
nodes[index] =
{
(2 * l.first * r.first +
l.first * r.second +
l.second * r.first ) % MOD,
(2 * l.second * r.second +
l.first * r.second +
l.second * r.first ) % MOD
};
}
void init(int N_, int M_, vector<int> P, vector<int> A_)
{
N = N_;
M = M_;
A = A_;
adj = vector<vector<int>>(N);
for (int i = 1; i < N + M; i++)
adj[P[i]].push_back(i);
nodes = vector<pair<ll, ll>>(N+M);
DFS(0);
}
int count_ways(int L, int R)
{
A[L - N] ^= 1;
while (1)
{
if (L >= N)
{
if (A[L - N])
nodes[L] = {1, 0};
else
nodes[L] = {0, 1};
L = (L - 1) / 2;
continue;
}
const auto l = nodes[adj[L][0]];
const auto r = nodes[adj[L][1]];
nodes[L] =
{
(2 * l.first * r.first +
l.first * r.second +
l.second * r.first ) % MOD,
(2 * l.second * r.second +
l.first * r.second +
l.second * r.first ) % MOD
};
if (L == 0) break;
L = (L - 1) / 2;
}
return nodes[0].first;
}
