背景

Update on 2022.12.18：新增一组针对

https://www.luogu.com.cn/user/421155

Update on 2022.12.18：新增一组针对 @大眼仔Happy 的 Hack 数据，放置于 #22，分值为 $5$ 分。

Update on 2025.7.7：新增两组 hack 数据，来自工单 https://www.luogu.com.cn/ticket/XQCA458514，放置于 #23、#24。#21~#24 全部改为 $0$ 分。

不可以，总司令。

题目描述

总司令给你一个长为 $n$ 的序列 $a$。

他认为这个 $a$ 现在也许不够优美，他希望将其重排为一个 $a'$，使之变得优美。

我们称一个长为 $n$ 的序列 $a$ 优美，当且仅当 $\exists i \in [1,n]$，满足：

• $\forall j \in [1, i)$，$a_j > a_{j + 1}$。
• $\forall j \in (i, n]$，$a_j > a_{j - 1}$。

他命令你求出 $a$ 经过重排可以得到多少个不同的 $a'$。由于结果可能很大，你只需要求出结果对 $p$ 取模的值。

由于一个固定的 $a$ 太无趣了，于是他给你 $m$ 次修改，每次修改形如 x k，表示令 $a_x \leftarrow k$。你需要在每次修改后求出当前的答案。

输入格式

第一行，三个整数 $n, m, p$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $m$ 行，每行两个整数 $x, k$，表示一次修改操作。

输出格式

共 $m + 1$ 行，每行一个整数，表示初始状态下及每次修改后所求的值。

4 1 998244353
1 2 2 3
3 4

2
8

见下发文件 sequence2.in

见下发文件 sequence2.out

提示

样例 #1 解释

对于初始状态，满足条件的 $a'$ 有 $[2, 1, 2, 3], [3, 2, 1, 2]$，共 $2$ 个。

对于第一次修改后的 $a = [1, 2, 4, 3]$，满足条件的 $a'$ 有 $[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [4, 1, 2, 3], [3, 2, 1, 4], [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]$，共 $8$ 个。

样例 #2 解释

该样例满足测试点 $15 \sim 20$ 的限制。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 \leq m \leq 5 \times 10^5$，$2 \leq p \leq 10^9$，$1 \leq a_i, k, x \leq n$。