题目描述

作为一名普及组选手，小 A 喜欢数数。

一天，小 A 学习了排列相关的知识。定义一个长度为 $n$ 的序列 $p_{1..n}$ 是一个 $n$ 阶排列，当且仅当 $p_{1..n}$ 都是 $[1, n]$ 中的正整数且它们两两不同。

小 A 想数排列。为了让数排列更有趣，小 A 决定加入一个限制：

对于一个 $n$ 阶排列 $p$，小 A 会构造一个长度为 $n$ 的序列 $Q(p)$，其中 $Q(p)_{p_i} = i$。

小 A 称排列 $p$ 是优秀的，当且仅当 $p$ 的字典序严格小于 $Q(p)$。即存在一个 $i$ 使得

$$\forall 1 \le j < i,\ p_j = Q(p)_j\ \text{且}\ p_i < Q(p)_i。$$

现在，小 A 想了一个数 $n$，他希望对于每个 $[1, n]$ 间的 $m$，计算好的 $m$ 阶排列数量。
在开始数这样的排列数量前，小 A 给了你一个质数 $\text{mod}$，希望你先求出好的 $m$ 阶排列数量对 $\text{mod}$ 取模的结果。

为了避免极其大的输出，设 $v_n$ 表示好的 $n$ 阶排列数量对 $\text{mod}$ 取模的结果，你只需要输出 $\oplus_{i=1}^n v_i$，即所有 $v_1, \dots, v_n$ 的异或和。这样小 A 在自己数错的时候就有大约 $1 - \frac{1}{\text{mod}}$ 的概率发现自己错了，并重新数一遍。

输入格式

输入文件包含一行两个正整数 $n, \text{mod}$，含义见题面。

输出格式

输出一个整数，表示 $\oplus_{i=1}^n v_i$。

样例

4 998244353

6

• $n = 1, 2$ 时，不存在好的排列。
• $n = 3$ 时，好的排列只有一个，为：$p = (2,3,1)$，$Q(p) = (3,1,2)$
• $n = 4$ 时，一共有 7 个好的排列，为：$$(1,3,4,2),\ (2,3,1,4),\ (2,3,4,1),\ (2,4,1,3),\ (2,4,3,1),\ (3,2,4,1),\ (3,4,2,1)$$因此答案为 $0 \oplus 0 \oplus 1 \oplus 7 = 6$。

7 998244353

2063

$v$ 依次等于：$0, 0, 1, 7, 47, 322, 2404$

100 1000000007

273351777

数据范围

对于所有测试点，保证 $n \leq 10^7$，$10^8 \leq \text{mod} \leq 1.05 \times 10^9$。

测试点编号	特殊限制
1,2	$n \leq 5$
3,4	$n \leq 10$
5,6,7,2	$n \leq 16$
8,9	$n \leq 30$
10,11	$n \leq 100$
12,13,14	$n \leq 2000$
15,16	$n \leq 2 \times 10^5$
17,18
19,20	无特殊限制

对于编号为奇数的测试点，额外保证 $\text{mod} = 998244353$。