有一个数字电路，由编号为从 $0$ 到 $N + M - 1$ 的 $N + M$ 个**门**组成。其中，$0$ 到 $N - 1$ 号门是**阈值门**，而 $N$ 到 $N + M - 1$ 号门是**输入门**。
除 $0$ 号门之外的每个门都是恰好一个某阈值门的**输入**。具体来说，对于每个满足 $1 \le i \le N + M - 1$ 的 $i$，门 $i$ 是门 $P[i]$ 的一个输入，其中 $0 \le P[i] \le N-1$。重要的是，我们保证 $P[i] \lt i$ 成立。此外，我们假设有 $P[0] = -1$。每个阈值门有一个或多个的输入。输入门没有任何输入。
每个门都有一个**状态**，取 $0$ 或 $1$。输入门的初始状态由一个包含 $M$ 个整数的数组 $A$ 给定。也就是说，对于每个满足 $0 \le j \le M - 1$ 的 $j$ ，输入门 $N + j$ 的初始状态为 $A[j]$。
每个阈值门的状态取决于它的输入的状态，具体如下。首先，每个阈值门会被指定一个阈值**参数**。对于一个有 $c$ 个输入的阈值门，其所指定的参数必须是 $1$ 到 $c$ 之间的某个整数（包括 $1$ 和 $c$）。随后，对于一个参数为 $p$ 的阈值门，如果它的输入中至少有 $p$ 个门的状态为 $1$，则当前阈值门的状态为 $1$，否则状态为 $0$。
例如，假设有 $N = 3$ 个阈值门和 $M = 4$ 个输入门。其中，门 $0$ 的输入为门 $1$ 和门 $6$，门 $1$ 的输入为门 $2$、$4$ 和 $5$，门 $2$ 仅有的输入为门 $3$。
上述例子的说明可见下图。
假设输入门 $3$ 和 $5$ 的状态为 $1$，而门 $4$ 和 $6$ 的状态为 $0$。假设阈值门 $2$、$1$、$0$ 被指定的参数分别为 $1$、$2$、$2$。在这种情况下，门 $2$ 的状态为 $1$，门 $1$ 的状态为 $1$ ，门 $0$ 的状态为 $0$。下面给出了参数赋值以及状态的示意图。状态为 $1$ 的门被标记为黑色。
输入门的状态将会经历 $Q$ 次更新。每次更新用两个整数 $L$ 和 $R$ 来描述 ($N \le L \le R \le N + M - 1$) ，表示翻转所有编号在 $L$ 和 $R$ 之间（包括 $L$ 和 $R$）的输入门的状态。这就是说，对于所有满足 $L \le i \le R$ 的 $i$，输入门 $i$ 的状态如果为 $0$，则会被翻转为$1$；如果状态为 $1$，则会被翻转为 $0$。每个门被翻转后将会一直保持在新状态，直到在后续某次更新中被翻转。
你的目标是，计算每次更新后有多少种阈值门参数的赋值方案，使得门 $0$ 的状态为 $1$。当有至少一个阈值门的参数不同时，两种参数赋值方案被认为是不同的。由于方案数可能较大，你需要计算它对 $1\;000\;002\;022$ 取模的结果。
注意，在上面的例子中，共有 $6$ 种不同的对阈值门参数进行赋值的方案，因为门 $0$、$1$、$2$ 分别有 $2$、$3$、$1$ 个输入。在这 $6$ 种方案里面，有 $2$ 种参数赋值方案使得门 $0$ 的状态为 $1$。
## Input
你的任务是实现下述两个函数。
```go
void init(int N, int M, int[] P, int[] A)
```
- $N$： 阈值门的数量。
- $M$：输入门的数量。
- $P$： 一个长度为 $N + M$ 的数组，给出阈值门的输入。
- $A$： 一个长度为 $M$ 的数组，给出输入门的初始状态。
- 这个函数被调用恰好一次，且发生在函数 `count_ways` 的所有调用之前。
```go
int count_ways(int L, int R)
```
- $L$, $R$：编号在 $L$ 和 $R$ 之间的输入门的状态将会被翻转。
- 这个函数应首先执行所规定的更新，然后返回使得门 $0$ 的状态为 $1$ 的参数赋值方案的方案数对 $1\;000\;002\;022$ 取模的结果。
- 这个函数会被调用恰好 $Q$ 次。
## Output
考虑如下的函数调用序列：
```go
init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])
```
题面描述中已经给出了对这个例子的解释。
```go
count_ways(3, 4)
```
这次调用翻转了门 $3$ 和 $4$ 的状态，也就是说，门 $3$ 的状态变成 $0$，门 $4$ 的状态变成 $1$。下面给出了两种可行的参数赋值方案，可以使得门 $0$ 的状态为 $1$ 。
| 方案 $1$ | 方案 $2$ |
| :-----------------------------------: | :-----------------------------------: |
|  |  |
在所有其他的参数赋值方案中，门 $0$ 的状态为 $0$。因此，函数应返回 $2$。
```go
count_ways(4, 5)
```
这次调用翻转了门 $4$ 和 $5$ 的状态。其结果是，所有输入门的状态均为 $0$，而且对于所有的参数赋值方案，门 $0$ 的状态均为 $0$。因此，函数应返回 $0$。
```go
count_ways(3, 6)
```
这次调用将所有输入门的状态置为 $1$。其结果是，对于所有参数赋值方案，门 $0$ 的状态均为 $1$。因此，函数应返回 $6$。
[samples]
## Background
**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**
这是一道交互题，你只需要实现代码中要求的函数。
你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。
由于本题数据点过多，结合洛谷评测技术实现情况，本题将不按照题给 Subtask 评分。
## Note
### 约束条件
- $1 \le N, M \le 10^5$；
- $1 \le Q \le 10^5$；
- $P[0] = -1$；
- $0 \le P[i] \lt i$ 且 $P[i] \le N - 1$（对于所有满足 $1 \le i \le N + M - 1$ 的 $i$）；
- 每个阈值门至少有一个输入（对于所有满足 $0 \le i \le N - 1$ 的 $i$，存在某个下标 $x$ 满足 $i \lt x \le N + M - 1$ 且 $P[x] = i$）；
- $0 \le A[j] \le 1$（对于所有满足 $0 \le j \le M - 1$的 $j$）；
- $N \le L \le R \le N + M - 1$。
### 子任务
1. （2 分）$N = 1$，$M \le 1000$，$Q \le 5$；
2. （7 分）$N, M \le 1000$，$Q \le 5$，每个阈值门都有恰好两个输入；
3. （9 分）$N, M \le 1000$，$Q \le 5$；
4. （4 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$）， $P[i] = \lfloor\frac{i - 1}{2}\rfloor$（对于所有满足 $1 \le i \le N + M - 1$ 的 $i$），$L = R$；
5. （12 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$），$P[i] = \lfloor\frac{i - 1}{2}\rfloor$（对于所有满足$1 \le i \le N + M - 1$的 $i$）；
6. （27 分）每个阈值门都恰好有两个输入；
7. （28 分）$N, M \le 5000$；
8. （11 分）没有额外的约束条件。
### 评测程序示例
评测程序示例读取如下格式的输入：
- 第 $1$ 行： $N \; M \; Q$；
- 第 $2$ 行： $P[0] \; P[1] \; \ldots \; P[N + M - 1]$；
- 第 $3$ 行： $A[0] \; A[1] \; \ldots \; A[M - 1]$；
- 第 $4 + k$ 行（$0 \le k \le Q - 1$）： 第 $k$ 次更新对应的 $L \; R$。
评测程序示例按照如下格式打印你的答案：
- 第 $1 + k$ 行（$0 \le k \le Q - 1$）： `count_ways` 函数对第 $k$ 次更新的返回值。
### 约定
题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。
在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：
| `void ` | `bool` | `int` | `int[]` |
| ------- | ------ | ------| ------------------ |
| `void ` | `bool` | `int` | `std::vector<int>` |
| `union(bool, int[])` | 数组 `a` 的长度 |
| -------------------------------------- | ------------------- |
| `std::variant<bool, std::vector<int>>` | `a.size()` |
C++ 语言里，`std::variant` 定义在 `<variant>` 头文件中。
一个返回类型为 `std::variant<bool, std::vector<int>>` 的函数可以返回一个 `bool` 或一个 `std::vector<int>`。
以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：
```cpp
std::variant<bool, std::vector<int>> foo(int N) {
return N % 2 == 0;
}
std::variant<bool, std::vector<int>> goo(int N) {
return std::vector<int>(N, 0);
}
std::variant<bool, std::vector<int>> hoo(int N) {
if (N % 2 == 0) {
return false;
}
return std::vector<int>(N, 0);
}
```