#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n, m;
vector<int> p, a;
vector<vector<int>> children;
const int modnum = 1000002022;
pair<ll, ll> calc(int x) {
int k = children[x].size();
vector<pair<ll, ll>> nums(k);
for (int i=0;i<k;i++) {
if (children[x][i] >= n) {
nums[i].ff = a[children[x][i] - n];
nums[i].ss = (a[children[x][i] - n] + 1) % 2;
} else {
nums[i] = calc(children[x][i]);
}
}
vector<ll> dum(k + 1);
vector<vector<ll>> one;
for (int i=0;i<k+1;i++) one.pb(dum);
for (int i=0;i<k+1;i++) {
one[i][0] = 0;
}
one[0][0] = 1;
one[0][1] = nums[0].ss;
for (int i=2;i<k+1;i++) {
one[0][i] = (one[0][i - 1] * nums[i - 1].ss) % modnum;
}
for (int i=1;i<k+1;i++) {
for (int j=1;j<k+1;j++) {
one[i][j] = (one[i][j - 1] * nums[j - 1].ss + one[i - 1][j - 1] * nums[j - 1].ff) % modnum;
}
}
/*
cout << x << " : " << endl;
for (int i=0;i<k;i++) {
cout << nums[i].ff << ' ' << nums[i].ss << endl;
} cout << endl;
for (int i=0;i<k+1;i++) {
for (int j=0;j<k+1;j++) {
cout << one[i][j] << ' ';
} cout << endl;
} cout << endl;
*/
ll zeronum = 0, onenum = 0;
for (int i=1;i<k+1;i++) {
for (int j=i;j<k+1;j++) {
onenum += one[j][k];
onenum %= modnum;
}
for (int j=0;j<i;j++) {
zeronum += one[j][k];
zeronum %= modnum;
}
}
//cout << "FINALS " << onenum << ' ' << zeronum << endl;
return mp(onenum, zeronum);
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N; m = M; p = P; a = A;
vector<int> dum;
for (int i=0;i<n+m;i++) {
children.pb(dum);
}
for (int i=1;i<n+m;i++) {
children[p[i]].pb(i);
}
/*
for (int i=0;i<n+m;i++) {
cout << i << " children ";
for (int j: children[i]) {
cout << j << ' ';
} cout << endl;
}
*/
}
int count_ways(int L, int R) {
int l = L, r = R;
for (int i=l;i<r+1;i++) {
a[i - n] = (a[i - n] + 1) % 2;
}
return calc(0).ff;
}
