优美序列

题目背景

在育华学校的算法竞赛集训中，T2之王遇到了一个关于序列重排的挑战。总司令要求将一个序列重排成"优美的序列"，并计算有多少种不同的重排方式。每次修改序列元素后，还需要重新计算结果。

题目描述

给定一个长度为 $n$ 的序列 $a$，可以将其重排为序列 $a'$。若存在位置 $i \in [1,n]$ 满足以下条件，则称 $a'$ 是"优美的"：

• 对于所有 $j \in [1, i)$，有 $a'_j > a'_{j+1}$（左侧严格递减）；
• 对于所有 $j \in (i, n]$，有 $a'_j > a'_{j-1}$（右侧严格递增）。

需要计算序列 $a$ 经过重排后能形成多少个不同的优美序列，结果对 $p$ 取模。此外，有 $m$ 次修改操作（每次将 $a_x$ 改为 $k$），每次修改后都需要重新计算答案。

输入格式

1. 第一行：三个整数 $n, m, p$，分别表示序列长度、修改次数、取模值；
2. 第二行：$n$ 个整数 $a_1, a_2, \cdots, a_n$，表示初始序列；
3. 接下来 $m$ 行：每行两个整数 $x, k$，表示将第 $x$ 个元素改为 $k$。

输出格式

共 $m+1$ 行，分别表示初始状态及每次修改后的答案（对 $p$ 取模）。

样例

样例输入 1

4 1 998244353
1 2 2 3
3 4

样例输出 1

2
8

样例解释 1

• 初始序列为 [1, 2, 2, 3]，优美序列有 2 个：[2, 1, 2, 3] 和 [3, 2, 1, 2]；
• 修改后序列为 [1, 2, 4, 3]，优美序列有 8 个，包括 [1, 2, 3, 4]、[2, 1, 3, 4] 等。

数据规模与测试点（育华学校专项）

注：所有测试点均满足 $2 \leq p \leq 10^9$，$1 \leq a_i, k, x \leq n$。