P16433 [APIO 2026 中国赛区] 上升
题目背景
提交时请选择高于 C++17 的语法标准，不要引入头文件 `ascend.h`。
题目描述
小 N 是一个喜欢事物呈上升趋势的女孩子，因为这往往意味着好事发生！
正是因为这样的爱好，对于一个 $1 \sim n$ 的排列 $q_1, q_2, \dots, q_n$，小 N 也喜欢研究其上升的位置。具体地，她定义排列 $q$ 中所有上升的位置构成的集合为 $S(q) = \{1 \le i < n \mid q_i < q_{i+1}\}$。
上升是一件幸运的事情，但具体有多幸运却是难以量化的。于是小 N 决定给排列里的每一个位置赋权，从而去量化幸运值。具体地，她给出了一个非负整数序列 $w_1, w_2, \dots, w_{n-1}$，并定义排列 $q$ 的 **幸运值** 为 $f(q) = \prod_{i \in S(q)} w_i$。特别地，若 $S(q) = \varnothing$，则 $f(q) = 1$。
小 C 是小 N 的好朋友，有一天，小 C 送了一个幸运的排列 $p_1, p_2, \dots, p_n$ 给她。但由于种种意外，排列中有些位置的元素缺失了，这些缺失位置的值变成了 $0$。
收到礼物后，小 N 并没有为排列的不完整而感到难过，因为她惊奇地发现：排列中 **所有未缺失位置上的元素仍是单调递增的**，即它们从左到右构成了一个单调递增的子序列。
小 N 顿时觉得自己是世界上最幸福的女孩子。同时，她也很好奇原来小 C 送的排列到底有多幸运。于是，她想要计算出符合 $p$ 的所有排列 $q$ 的幸运值 $f(q)$ 之和。其中排列 $q$ 符合 $p$ 当且仅当：对于所有 $1 \le i \le n$，均有 $p_i = 0$ 或 $q_i = p_i$。
你的任务是帮助小 N 求出，符合 $p$ 的所有排列 $q$ 的幸运值之和。
### 【实现细节】
选手不需要，也不应该实现 `main` 函数。
选手需要确保提交的程序包含头文件 `ascend.h`，即在程序开头加入以下代码：
```cpp
#include "ascend.h"
```
选手需要在提交的程序源文件 `ascend.cpp` 中实现以下函数：
```cpp
int ascend(int c, int n, int m, std::vector p, std::vector w);
```
* $c, n$ 分别表示测试点编号、排列的长度。$c = 0$ 表示该测试点为样例。
* $p$ 表示缺失了若干个位置后的小 C 的排列。对于 $0 \le i < n$，$p_i$ 表示缺失后的排列的第 $i + 1$ 位的值。
* $w$ 表示小 N 的权值序列。对于 $0 \le i < n - 1$，$w_i$ 表示第 $i + 1$ 个位置的权值。
* 该函数需要返回符合 $p$ 的所有排列 $q$ 的幸运值 $f(q)$ 之和对 $m$ 取模后的结果。
* 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。
### 【测试程序方式】
选手可以在本题目录下使用如下命令编译得到可执行程序：
```bash
g++ grader.cpp ascend.cpp -o ascend -O2 -std=c++14 -static
```
输入格式
对于编译得到的可执行程序：
* 可执行文件将从标准输入读入以下格式的数据：
* 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。
* 接下来依次为每组测试数据，对于每组测试数据：
* 第一行包含两个正整数 $n, m$。
* 第二行包含 $n$ 个非负整数 $p_1, p_2, \dots, p_n$。
* 第三行包含 $n - 1$ 个非负整数 $w_1, w_2, \dots, w_{n-1}$。
输出格式
* 可执行文件将输出以下格式的数据至标准输出：
* 对于每组测试数据，输出一行一个非负整数，表示 `ascend` 函数的返回值。
说明/提示
### 【样例 1 解释】
共有以下两个排列 $q$ 符合排列 $p$：
1. $q = [1, 2, 3], S(q) = \{1, 2\}, f(q) = w_1 \times w_2 = 2 \times 3 = 6$;
2. $q = [3, 2, 1], S(q) = \varnothing, f(q) = 1$。
因此，符合 $p$ 的所有排列的幸运值之和为 $6 + 1 = 7$，对 $m = 6$ 取模后的结果为 $1$。
### 【数据范围】
对于所有测试数据，均有：
* $1 \le t \le 5$;
* $2 \le n \le 500$, $2 \le m \le 10^9$;
* 对于所有 $1 \le i \le n$，均有 $0 \le p_i \le n$;
* 序列 $p$ 中所有不为 $0$ 的元素构成一个单调递增的子序列;
* 对于所有 $1 \le i \le n-1$，均有 $0 \le w_i < m$。
::cute-table{tuack}
|测试点编号|$n \le$|特殊性质|
|:-:|:-:|:-:|
|$1,2$|$10$|无|
|$3,4$|$20$|^ |
|$5 \sim 7$|$500$|A|
|$8 \sim 10$|$50$|B|
|$11 \sim 13$|$150$| ^|
|$14 \sim 18$|$500$| ^|
|$19,20$| ^|无|
- 特殊性质 A：对于所有 $1 \le i \le n$，均有 $p_i = 0$。
- 特殊性质 B：$m \ge 5 \times 10^8$ 且 $m$ 为素数。