题目描述

我是易云龙，我喜欢出阴间 Round。 $\color{white}{\text{zsq orz}}$

给你有一个长度为 $n$ 的括号序列 $c$，定义合法的括号序列如下： $\color{white}{\text{zsq orz}}$

1. 空串是合法的括号序列。 $\color{white}{\text{zsq orz}}$

2. 若 $A$ 和 $B$ 是合法的括号序列，则 $AB$ 也是合法的括号序列。 $\color{white}{\text{zsq orz}}$

3. 若 $A$ 是合法的括号序列，则 $(A)$ 也是合法的括号序列。 $\color{white}{\text{zsq orz}}$

定义一个排列 $p$ 是合法的，当且仅当括号序列 $d(\forall i \in [1,n],d_i=c_{p_i})$ 是合法的括号 序列，定义 $c$ 的价值为所有好的排列的逆序数总和。$c$ 并不稳定，会发生 $q$ 次改变，具体来说，$c$ 中的某两个元素会发生交换。（改变是 永久的） 你需要对一开始的 $c$ 和每次改变后的 $c$ 分别求出它的所有子序列的价值和对质数 $P$ 取模的结果。 $\color{white}{\text{zsq orz}}$

输入格式

第一行三个非负整数 $n$, $q$, $P$，意义如题面所示。 第二行一个 32 位无符号整数 $seed$，表示随机数生成器的种子，用来生成括号序列 $c$，和修改的 $u$, $v$。你可以在选手文件夹下的 bracket/generator.cpp 文件内了解如何生成 初始的括号序列和修改。 $\color{white}{\text{zsq orz}}$

输出格式

请以哈希方式输出答案。 $\color{white}{\text{zsq orz}}$

具体来说，设答案分别为 $a_0$, $a_1$, $\dots$, $a_q$。 你只需要输出 $\bigoplus_{i=0}^q(a_i \times (i+1) \bmod P)$。 $\color{white}{\text{zsq orz}}$

样例 1 输入

2 2 998244853
2387462378

样例 1 输出

2

样例 2 输入

20 100 998244353
1451367960

样例 2 输出

197747207

样例 3 输入

4557220 5000000 903563477 2604393553

样例 3 输出

340188558

数据规模与约定

对于 $100\%$ 的数据，满足：$1 \leq n,q \leq 5 \times 10^6$ 且 n 是偶数，$n < P \leq 10^9$ 且 $P$ 是质数，$ 0\leq seed < 2^{32}$。 $\color{white}{\text{zsq orz}}$

具体的数据范围见下表：

$\color{white}{\text{zsq orz}}$