#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
const int MOD = 1000002022;
v<v<int>> adj;
v<v<int>> rev;
v<int> in;
v<int> pref;
int n;
int t;
void dfs1(int u, int p=-1) {
in[u] = t;
//cout << u << " " << t << endl;
t--;
for (auto x : rev[u]) {
//cout << x << " ";
if (x != p && x < n) {
dfs1(x, u);
}
}
//cout << endl;
}
v<int> s;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
s = A;
int NM = P.size();
v<int> par(n, 0);
adj.resize(NM);
rev.resize(NM);
rep(i, 1, NM) {
par[P[i]]++;
}
//cout << N << endl;
rep(i, 1, NM) {
adj[i].push_back(P[i]);
rev[P[i]].push_back(i);
}
in.resize(n);
t = n-1;
dfs1(0);
v<int> a(n);
rep(i, 0, n) {
a[in[i]] = par[i];
//cout << in[i] << " " << par[i] << " " << i << endl;
}
pref.resize(n);
pref[0] = a[0];
rep(i, 1, n) {
pref[i] = pref[i-1] * a[i];
pref[i] %= MOD;
}
//rep(i, 0, n) cout << pref[i] << " ";
}
ll backtrack(int u) {
//cout << u << endl;
int bl = 0;
int p = -1;
int cnt = 0;
for (auto x : rev[u]) {
if (x < n) p = x;
else {
bl += s[x-n];
// cout << x << " " << s[x-n] << endl;
}
}
//cout << u << " "<< p << " " << bl << endl;
ll ans = 0;
if (p==-1) {
if (bl == 1) return 1;
else if (bl == 2) return 2;
else return 0;
}
if (bl == 1) {
ans += pref[in[p]];
ans %= MOD;
ans += backtrack(p);
ans %= MOD;
}
else {
ans += backtrack(p);
ans %= MOD;
}
return ans;
}
int count_ways(int L, int R) {
L -= n, R -= n;
int m = s.size();
rep(i, L, R+1) {
s[i] ^= 1;
//cout << i << " " << s[i] << endl;
}
ll ans = backtrack(0);
ans %= MOD;
int ansi = ans;
return ansi;
}
