#include "circuit.h" #include <bits/stdc++.h> #define int long long const int mod = 1e9+2022; using namespace std; int n,m; vector<int> p,v; vector<int> coeff; int ans = 0; void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) { n = N,m = M; p.resize(n+m),v.resize(m); vector<int> mult(n+m,1); coeff.resize(m); vector<vector<int>> graph(n+m); for(int i = 0; i < n+m; i++) p[i] = P[i]; for(int i = 0; i < m; i++) v[i] = A[i]; for(int i = 1; i < n+m; i++) graph[p[i]].push_back(i); vector<int> hlp(n+m,1); function<void(int)> dfs = [&](int cur) { if(graph[cur].empty())return; for(int a: graph[cur]) dfs(a); int k = graph[cur].size(); vector<int> suf(k,1); vector<int> pref(k,1); for(int i = 0; i < k; i++) pref[i] = (i>0?pref[i-1]:1)*mult[graph[cur][i]]%mod; for(int i = k-1; i >= 0; i--) suf[i] = (i<k-1?suf[i+1]:1)*mult[graph[cur][i]]%mod; for(int i = 0; i <k;i++) hlp[graph[cur][i]]=(i>0?pref[i-1]:1)*(i<k-1?suf[i+1]:1)%mod; for(int a :graph[cur]) mult[cur]=mult[a]*mult[cur]%mod; mult[cur]=k*mult[cur]%mod; }; dfs(0); function<void(int,int)> pass = [&](int cur,int run){ if(cur>=n) coeff[cur-n] = run*hlp[cur]%mod; else { for(int a: graph[cur]) pass(a,run*hlp[cur]%mod); } }; pass(0,1); for(int i = 0; i < m; i++) ans+=v[i]*coeff[i]%mod; ans%=mod; } signed count_ways(signed L, signed R) { for(int i = L-n; i <= R-n; i++) ans-=coeff[i]*v[i]-coeff[i]*(1-v[i]),v[i] = 1-v[i]; ans=(ans+m*mod+mod)%mod; return ans; }