#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int p1=0, n, m;
vector<int> p, a;
vector<vector<int>> in(1e3+3);
void _p1() {
p1=1;
}
void init(int N, int M, vector<int> P, vector<int> A) {
n=N, m=M, p=P, a=A;
if (n==1) _p1();
for (int i=1; i<n+m; ++i) {
in[p[i]].push_back(i);
}
}
int count_ways(int l, int r) {
for (int i=l-n; i<=r-n; ++i) a[i]^=1;
if (p1) {
int s=0;
for (int i=0; i<m; ++i) s+=a[i];
return s;
}
vector<vector<ll>> dp(n,{0,0});
for (int i=n-1; i>=0; --i) {
int cnt=0;
int inp=0;
int f=-1;
for (auto x:in[i]) {
if (x>=n) cnt+=a[x-n];
else f=x;
inp+=x>=n;
}
if (inp==2) {
dp[i]={2-cnt,cnt};
} else if (inp==1) {
if (cnt) {
dp[i][1]=dp[f][0]+dp[f][1]+dp[f][1];
dp[i][0]=dp[f][0];
} else {
dp[i][1]=dp[f][1];
dp[i][0]=dp[f][1]+dp[f][0]+dp[f][0];
}
} else {
int s=in[i][0];
dp[i][1]=(1ll*dp[f][1]*(dp[s][0]+dp[s][1])+1ll*dp[s][1]*(dp[f][0])+1ll*dp[s][1]*dp[f][1])%1000002022;
dp[i][0]=(1ll*dp[f][0]*dp[s][0]+1ll*dp[f][0]*dp[s][0]+1ll*dp[f][1]*dp[s][0]+1ll*dp[s][1]*dp[f][0])%1000002022;
}
}
//for (auto x:dp) cout<<x[1]<<' '<<x[0]<<'\n';
return dp[0][1];
}
