#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> info(2020);
vector<vector<ll>> g(2020);
ll n, m;
const ll mod = (1e9 + 2022);
void dfs(ll node, vector<vector<ll>> &g, vector<vector<ll>> &cnt){
for(ll i : g[node]) dfs(i, g, cnt);
ll c = g[node].size();
if(c == 0){
cnt[0][node] = (info[node] == 0);
cnt[1][node] = (info[node] == 1);
return;
}
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(c, vector<ll>(c)));
vector<ll> suff_zeros(c+1, 1);
for(ll i = c-1; i >= 0; i--) suff_zeros[i] = (cnt[0][g[node][i]] * suff_zeros[i+1]) % mod;
dp[1][1][0] = cnt[1][g[node][0]];
for(ll i = 0; i < c; i++) dp[1][0][i] = cnt[0][i];
for(ll k = 1; k <= c; k++){
for(ll j = 0; j < c; j++){
dp[1][k][j] = dp[1][k-1][j-1] * cnt[1][g[node][j]] * suff_zeros[j+1];
}
}
}
void binary_tree_dfs(ll n, vector<vector<ll>> &dp){
if(g[n].size() == 0){
dp[1][n] = (info[n] == 1);
dp[0][n] = (info[n] == 0);
return;
}
for(ll i: g[n]) {
binary_tree_dfs(i, dp);
}
ll a = g[n][0], b = g[n][1];
dp[1][n] = dp[1][a] * dp[0][b] + dp[1][b] * dp[0][a] + 2 * dp[1][a] * dp[1][b];
dp[0][n] = dp[1][a] * dp[0][b] + dp[1][b] * dp[0][a] + 2 * dp[0][a] * dp[0][b];
}
void init(int N, int M, std::vector<int> p, std::vector<int> a) {
n = N, m = M;
for(ll i = 1; i < n+m; i++) g[p[i]].push_back(i);
for(ll i = 0; i < m; i++) info[n + i] = a[i];
}
int count_ways(int l, int r) {
for(ll i = l; i <= r; i++) info[i] ^= 1;
vector<vector<ll>> dp(2, vector<ll>(n+m));
binary_tree_dfs(0, dp);
return dp[1][0];
}
