#include "circuit.h"

#include <bits/stdc++.h>

using namespace std;
const int N = (int)1e5 + 12, MOD = 1000002022;

typedef long long ll;

int n, m, f, a[N];
vector<int> g[N], dp[N];
void add(int &x, int y) {
    x += y;
    if(x >= MOD) x -= MOD;
}
int pd[N][2];
void dfs(int v) {
    if(v >= n) {
        pd[v][a[v]] = 1;
        pd[v][1 - a[v]] = 0;
        return;
    }
    int sz = (int)g[v].size();
    for(int i = 0; i <= sz; i++) {
        dp[v][i] = 0;
    }
    dp[v][0] = 1;
    ll f = 1;
    for(int to : g[v]) {
        dfs(to);
        int x = pd[to][1], y = pd[to][0];
        for(int i = sz; i >= 0; i--) {
            dp[v][i] = (dp[v][i] * 1ll * y) % MOD;
            if(i) add(dp[v][i], dp[v][i - 1] * 1ll * x % MOD);
        }
    }
    pd[v][0] = dp[v][0] * 1ll * sz % MOD;
    pd[v][1] = 0;   
    for(int i = 1; i <= sz; i++) {
        add(pd[v][1], dp[v][i] * 1ll * (i) % MOD);
        add(pd[v][0], dp[v][i] * 1ll * (sz - i) % MOD);
    }
}
void init(int NN, int MM, vector<int> P, vector<int> A) {
    n = NN;
    m = MM;
    f = n + m;
    for(int i = n; i < f; i++) {
        a[i] = A[i - n];
    }
    for(int i = 1; i < f; i++) {
        g[P[i]].push_back(i);
    }

    for(int i = 0; i < f; i++) {
        dp[i].resize((int)g[i].size() + 1);
    }
}

int count_ways(int L, int R) {
    for(int i = L; i <= R; i++) {
        a[i] ^= 1;
    }
    dfs(0);
    assert(pd[0][1] >= 0);
    return pd[0][1];
}