#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1'000'002'022;
const int MAXN = 2e5;
vector <int> adj[MAXN+5];
ll dp[MAXN+5][2], state[MAXN+5], N, M;
void dfs(ll idx) {
if (idx >= N) {
dp[idx][state[idx]] = 1;
dp[idx][!state[idx]] = 0;
return;
}
ll prod = 1;
dp[idx][0] = dp[idx][1] = 0;
for (auto i : adj[idx]) {
dfs(i);
vector <ll> ndp(2);
ndp[0] += dp[idx][0]*(dp[i][0]+dp[i][1])%MOD;
ndp[0] += prod*dp[i][0]%MOD;
ndp[0] %= MOD;
ndp[1] += dp[idx][1]*(dp[i][0]+dp[i][1])%MOD;
ndp[1] += prod*dp[i][1]%MOD;
ndp[1] %= MOD;
prod *= (dp[i][0]+dp[i][1]);
prod %= MOD;
for (int j = 0; j < 2; j++) {
dp[idx][j] = ndp[j];
}
}
}
void init(int n, int m, vector<int> P, vector<int> A) {
N = n, M = m;
for (int i = 1; i < N+M; i++) {
adj[P[i]].push_back(i);
}
for (int i = 0; i < M; i++) {
state[i+N] = A[i];
}
}
int count_ways(int L, int R) {
for (int i = L; i <= R; i++) state[i] ^= 1;
dfs(0);
return dp[0][1];
}
