#include "circuit.h"

#include <bits/stdc++.h>

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

typedef long long ll;

int n, m, f, a[N], p[N], dep[N];
vector<int> g[N], dp[N], G[N];

int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
void prec(int v) {
    for(int to : G[v]) {
        if((int)G[to].size() == 1 && to < n) {
            p[to] = v;
        }
        prec(to);
    }
}
int mx = 0;
void go(int v) {
    mx = max(mx, dep[v]);
    for(int to : g[v]) {
        dep[to] = dep[v] + 1;
        go(to);
    }
}
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 = 0; i < f; i++) {
        p[i] = i;
    }
    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);
    }
    prec(0);

    for(int i = 0; i < n; i++) {
        for(int to : G[i]) {
            int x = get(i),y = get(to);
            if(x != y) {
                g[x].push_back(y);
            }
        }
    }
    for(int i = 0; i < f; i++) {
        dp[i].resize((int)g[i].size() + 1);
    }
    go(0);
    assert(mx <= 20);
}

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];
}