#216474. [APIO 2026 中国赛区] 上升

提交时请选择高于 C++17 的语法标准，不要引入头文件 ascend.h。

小 N 是一个喜欢事物呈上升趋势的女孩子，因为这往往意味着好事发生！

正是因为这样的爱好，对于一个 的排列 ，小 N 也喜欢研究其上升的位置。具体地，她定义排列 中所有上升的位置构成的集合为 。

上升是一件幸运的事情，但具体有多幸运却是难以量化的。于是小 N 决定给排列里的每一个位置赋权，从而去量化幸运值。具体地，她给出了一个非负整数序列 ，并定义排列 的 幸运值 为 。特别地，若 ，则 。

小 C 是小 N 的好朋友，有一天，小 C 送了一个幸运的排列 给她。但由于种种意外，排列中有些位置的元素缺失了，这些缺失位置的值变成了 。

收到礼物后，小 N 并没有为排列的不完整而感到难过，因为她惊奇地发现：排列中 所有未缺失位置上的元素仍是单调递增的，即它们从左到右构成了一个单调递增的子序列。

小 N 顿时觉得自己是世界上最幸福的女孩子。同时，她也很好奇原来小 C 送的排列到底有多幸运。于是，她想要计算出符合 的所有排列 的幸运值 之和。其中排列 符合 当且仅当：对于所有 ，均有 或 。

你的任务是帮助小 N 求出，符合 的所有排列 的幸运值之和。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 ascend.h，即在程序开头加入以下代码：

#include "ascend.h"

选手需要在提交的程序源文件 ascend.cpp 中实现以下函数：

int ascend(int c, int n, int m, std::vector<int> p, std::vector<int> w);

• 分别表示测试点编号、排列的长度。 表示该测试点为样例。
• 表示缺失了若干个位置后的小 C 的排列。对于 ， 表示缺失后的排列的第 位的值。
• 表示小 N 的权值序列。对于 ， 表示第 个位置的权值。
• 该函数需要返回符合 的所有排列 的幸运值 之和对 取模后的结果。
• 对于每个测试点，该函数会被交互库调用恰好 次。

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp ascend.cpp -o ascend -O2 -std=c++14 -static

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 ，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据：
    • 第一行包含两个正整数 。
    • 第二行包含 个非负整数 。
    • 第三行包含 个非负整数 。

• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行一个非负整数，表示 ascend 函数的返回值。

样例输入 1

0 1
3 6
0 2 0
2 3

样例输出 1

1

【样例 1 解释】

共有以下两个排列 符合排列 ：

1. ;
2. 。

因此，符合 的所有排列的幸运值之和为 ，对 取模后的结果为 。

【数据范围】

对于所有测试数据，均有：

• ;
• , ;
• 对于所有 ，均有 ;
• 序列 中所有不为 的元素构成一个单调递增的子序列;
• 对于所有 ，均有 。

::cute-table{tuack} |测试点编号||特殊性质| |:-:|:-:|:-:| |||无| |||^ | |||A| |||B| ||| ^| ||| ^| || ^|无|

• 特殊性质 A：对于所有 ，均有 。
• 特殊性质 B： 且 为素数。