#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
template<typename traits>
class Mod_Int{
public:
using int_t = typename traits::int_t;
using long_t = typename traits::long_t;
static constexpr int_t mod(){ return traits::get_mod(); };
struct Summer{
public:
static constexpr long_t modmod(){ return traits::get_mod()*(long_t)traits::get_mod(); };
static long_t modmod_step(long_t const& val){
return val >= modmod() ? val-modmod() : val;
}
Summer() : val{} {}
explicit Summer(Mod_Int const&o) : val(o.get_value()){}
operator Mod_Int() const {
return Mod_Int(mod_full(val));
}
Summer operator-(Summer const&o){
return Summer(modmod() - modmod_step(o.val));
}
Summer& operator+=(Summer const&o){
val = modmod_step(val+o.val);
return *this;
}
Summer& operator-=(Summer const&o){
return operator-=(-o);
}
Summer& addmul(Mod_Int const&a, Mod_Int const&b){
val = modmod_step(val + a.get_value()*(long_t)b.get_value());
return *this;
}
private:
long_t val;
};
Mod_Int() : value(0) {}
Mod_Int(int_t value_) : value(value_) {}
friend ostream& operator<<(ostream&o, Mod_Int const&val){
return o << val.value;
}
friend istream& operator>>(istream&i, Mod_Int &val){
i >> val.value;
val.value = mod_full(val.value);
return i;
}
int_t const& get_value() const {
return value;
}
Mod_Int operator+(Mod_Int const&o) const {
Mod_Int ret(mod_step(value + o.value));
return ret;
}
Mod_Int& operator+=(Mod_Int const&o){
return *this = *this + o;
}
Mod_Int& operator++(){
return operator+=(int_t{1});
}
Mod_Int operator-() const{
Mod_Int ret(mod_step(mod() - value));
return ret;
}
Mod_Int operator-(Mod_Int const&o) const {
return operator+(-o);
}
Mod_Int& operator-=(Mod_Int const&o){
return operator+=(-o);
}
Mod_Int& operator--(){
return operator-=(int_t{1});
}
friend Mod_Int operator*(Mod_Int const&a, Mod_Int const&b) {
Mod_Int ret(mod_full(a.value * static_cast<long_t>(b.value)));
return ret;
}
Mod_Int& operator*=(Mod_Int const&o){
return *this = *this * o;
}
Mod_Int inv() const {
return inv_impl(value);
}
Mod_Int operator/(Mod_Int const&o) const {
return *this * o.inv();
}
Mod_Int& operator/=(Mod_Int const&o) {
return *this = *this / o;
}
bool operator==(Mod_Int const&o) const {
return value == o.value;
}
bool operator!=(Mod_Int const&o) const {
return !(*this == o);
}
bool operator!() const {
return !value;
}
private:
static int_t mod_step(int_t const& val){
return val >= mod() ? val-mod() : val;
}
static int_t mod_full(long_t const&val){
return mod() ? val%mod() : val;
}
static Mod_Int inv_impl(Mod_Int const& val){
if(mod() == 0){
assert(val*val == 1);
return val;
}
int_t value = val.value;
constexpr size_t cache_size = traits::inv_cache_size()+1;
static_assert(cache_size > 1);
static array<Mod_Int, cache_size> cache = [](){
array<Mod_Int, cache_size> ret;
ret[1] = 1;
for(int_t i=2;i<cache_size && i < mod();++i){
ret[i] = -ret[mod()%i] * (mod()/i);
}
return ret;
} ();
assert(value != 0);
Mod_Int factor = 1;
while(value >= cache_size){
factor *= - Mod_Int(mod() / value);
value = mod() % value;
}
assert(value != 0);
assert(factor != 0 && value != 0);
return factor * cache[value];
}
int_t value;
};
template<uint32_t mod>
struct fixed_mod{
using int_t = uint32_t;
using long_t = uint64_t;
static_assert(mod != 0, "Negative numbers won't work.");
static_assert(numeric_limits<int_t>::max()/2 >= mod, "Addition might overflow.");
static constexpr size_t inv_cache_size(){ return 30000; }
static constexpr int_t get_mod(){ return mod; }
};
#ifdef __SIZEOF_INT128__
template<uint64_t mod>
struct fixed_mod_long{
using int_t = uint64_t;
using long_t = __int128;
static_assert(mod != 0, "Negative numbers won't work.");
static_assert(numeric_limits<int_t>::max()/2 >= mod, "Addition might overflow.");
static constexpr size_t inv_cache_size(){ return 30000; }
static constexpr int_t get_mod(){ return mod; }
};
#endif // __SIZEOF_INT128__
struct no_mod{
using int_t = int64_t;
using long_t = int_t;
static constexpr size_t inv_cache_size(){ return 1; }
static constexpr int_t get_mod(){ return 0; }
};
struct mutable_mod{
using int_t = uint32_t;
using long_t = uint64_t;
static int_t mod;
// can't use cache if mod is changing
static constexpr size_t inv_cache_size(){ return 1; }
static int_t get_mod(){ return mod; }
};
mutable_mod::int_t mutable_mod::mod = 1000000007;
using num = Mod_Int<fixed_mod<1'000'002'022> >;
//really fast iterative segment-tree implementation
template<class Segtree_Data>
struct Segtree{
int N, height;
vector<typename Segtree_Data::node_t> data;
vector<typename Segtree_Data::update_t> lazy;
Segtree(vector<typename Segtree_Data::node_t> const&base):N(base.size()), height(__builtin_clz(1)-__builtin_clz(N)), data(2*N, Segtree_Data::node_ne()), lazy(2*N, Segtree_Data::update_ne()){
copy(base.begin(), base.end(), data.begin()+N);
for(int i=N-1;i>=0;--i)
data[i]=Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
}
Segtree(int n):N(n), height(__builtin_clz(1)-__builtin_clz(N)), data(2*N, Segtree_Data::node_ne()), lazy(2*N, Segtree_Data::update_ne()){
for(int i=N-1;i>=0;--i)
data[i]=Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
}
void local_update(int pos, typename Segtree_Data::update_t const&val){
Segtree_Data::update_node(data[pos], val);
if(pos<N) lazy[pos] = Segtree_Data::merge_lazy(lazy[pos], val);
}
void push(int pos){
for(int s=height;s>0;--s){
int i=pos>>s;
if(lazy[i]!=Segtree_Data::update_ne()){
local_update(i<<1, lazy[i]);
local_update(i<<1|1, lazy[i]);
lazy[i]=Segtree_Data::update_ne();
}
}
}
void re_path(int pos){
while(pos>>=1) Segtree_Data::update_node(data[pos] = Segtree_Data::merge_nodes(data[pos<<1], data[pos<<1|1]), lazy[pos]);
}
void update(int l, int r, typename Segtree_Data::update_t const&val){
int l2=l+=N, r2=r+=N;
push(l2); push(r2-1);
for(;l<r;l>>=1, r>>=1){
if(l&1) local_update(l++, val);
if(r&1) local_update(--r, val);
}
re_path(l2);re_path(r2-1);
}
typename Segtree_Data::node_t query(int l, int r){
push(l+N); push(r+N-1);
typename Segtree_Data::node_t retL=Segtree_Data::node_ne(), retR=Segtree_Data::node_ne();
for(l+=N, r+=N;l<r;l>>=1, r>>=1){
if(l&1)retL=Segtree_Data::merge_nodes(retL, data[l++]);
if(r&1)retR=Segtree_Data::merge_nodes(data[--r], retR);
}
return Segtree_Data::merge_nodes(retL, retR);
}
};
struct Node{
num on, off;
};
struct Segtreedata{
typedef Node node_t;
typedef int update_t;
static node_t node_ne() {return Node{0, 0};}
static update_t update_ne(){return 0;}
static node_t merge_nodes(node_t const&left, node_t const&right){
return Node{left.on+right.on, left.off+right.off};
}
static void update_node(node_t &node, update_t const&update){
if(update % 2){
swap(node.on, node.off);
}
}
static update_t merge_lazy(update_t const&old, update_t const&update){
return old + update;
}
};
Segtree<Segtreedata> st(0);
int NN, MM;
void init(int N, int M, vector<int> p, vector<int> a) {
MM = M; NN=N;
// [0, N) is computed, [N, N+M) is given
vector<vector<int> > ch(N);
for(int i=1; i<N+M; ++i) ch[p[i]].push_back(i);
vector<num> states(N+M, num(1));
vector<num> down(N+M, num(1));
vector<num> pre, suff;
for(int i=N-1; i>=0; --i){
auto &e = ch[i];
const int d = ch[i].size();
pre.assign(d+1, num(1));
suff.assign(d+1, num(1));
for(int j=0; j<d; ++j){
pre[j+1] = pre[j] * states[e[j]];
}
for(int j = d-1; j>=0; --j){
suff[j] = suff[j+1] * states[e[j]];
}
for(int j=0; j<d; ++j){
down[e[j]] = pre[j] * suff[j+1];
}
states[i] = pre.back() * num(d);
}
for(int i=1; i<N+M; ++i){
down[i] *= down[p[i]];
}
/*for(int i=N; i<N+M; ++i){
cerr << down[i] << " ";
}
cerr << "\n";*/
vector<Node> base(M);
for(int i=0; i<M; ++i){
base[i] = a[i] ? Node{down[N+i], 0} : Node{0, down[N+i]};
// base[i] = Node{down[N+i], 0};
}
st = decltype(st)(base);
}
int count_ways(int L, int R) {
L -= NN;
R -= NN;
++R;
st.update(L, R, 1);
const num ans = st.query(0, MM).on;
return ans.get_value();
}
