#include "circuit.h"
#include <bits/stdc++.h>
using namespace std; 
const int P = 1000002022; 
const int N = 1e5 + 5; 

int n, m, fa[N * 2], c[N * 2], a[N], w[N], mul[N]; 
int pre[N], suf[N], id[N]; 
vector<int> G[N * 2]; 

void dfs(int x) {
    c[x] = G[x].size(); 
    if (c[x] == 0) mul[x] = 1; 
    else mul[x] = c[x]; 
    for (int y : G[x]) dfs(y), mul[x] = 1ll * mul[x] * mul[y] % P; 
}
void dfs2(int x) {
    if (c[x] == 0) return; 
    int tot = 0; 
    for (int y : G[x])
        id[y] = ++tot, pre[tot] = suf[tot] = mul[y]; 
    pre[0] = 1; suf[tot + 1] = 1; 
    for (int i = 1; i <= tot; ++i) pre[i] = 1ll * pre[i] * pre[i - 1] % P; 
    for (int i = tot; i >= 1; --i) suf[i] = 1ll * suf[i] * suf[i + 1] % P; 
    for (int y : G[x]) 
        w[y] = 1ll * w[x] * pre[id[y] - 1] % P * suf[id[y] + 1] % P; 
    for (int y : G[x]) dfs2(y); 
}

// 贡献是 1 / (一个节点到根的路径上所有儿子的乘积)
// 也就是 一个节点到根的路径上排除当前儿子的乘积
int T[N * 4][2], tag[N * 4]; 
inline void pushup(int o) {
    for (int i = 0; i < 2; ++i)
        T[o][i] = (T[o << 1][i] + T[o << 1 | 1][i]) % P; 
}
void build(int o, int l, int r) {
    if (l == r) {
        if (a[l] == 1) T[o][1] = w[l + n]; 
        else T[o][0] = w[r + n]; 
        return; 
    }
    int mid = (l + r) >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 
    pushup(o); 
}
inline void maketag(int o) { swap(T[o][0], T[o][1]); tag[o] ^= 1; }
inline void pushdown(int o) {
    if (!tag[o]) return; 
    tag[o] = 0; 
    maketag(o << 1); maketag(o << 1 | 1); 
}
void update(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return maketag(o); 
    pushdown(o); int mid = (l + r) >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y); 
    pushup(o); 
}

int count_ways(int L, int R) {
    ++L; ++R; 
    update(1, 1, m, L - n, R - n); 
    return T[1][1]; 
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M; 
    for (int i = 0; i < m; ++i) a[i + 1] = A[i]; 
    for (int i = 0; i < int(P.size()); ++i)
        if (P[i] != -1) G[P[i] + 1].emplace_back(i + 1), fa[i + 1] = P[i] + 1; 
    dfs(1); w[1] = 1; dfs2(1); build(1, 1, m); 
    for (int i = 1; i <= n + m; ++i)
        cerr << w[i] << " \n"[i == n + m]; 
}