题目描述

Chino 想要用现在手里有的 $n$ 道题出成一套模拟赛。一开始，这 $n$ 道题按照由易到难的顺序排列。

但是因为 Chino 是一个可爱的妹子，所以她会将这些题目的顺序打乱。具体地，她会执行恰好奇数次操作，每次操作她会将其中两道题的位置交换。一套可能的模拟赛就是这些题的一个排列。

Chino 为了评估一套模拟赛的可爱程度，她定义 $s$ 表示使得开始时的题目顺序变为这套模拟赛的题目顺序的最少操作次数，定义 $t$ 表示开始时与这套模拟赛中位置相同的题目数量，那么这套模拟赛的可爱程度就是 $s/\left(t+1\right)$。

按照套路，你现在应该帮 Chino 计算某一套模拟赛的可爱程度。Chino 觉得这不够可爱，所以她想让你计算所有可能的模拟赛的可爱程度的两倍和。可以发现这一定是一个非负整数。为了避免答案过大，你只需要输出其对质数 $p$ 取模后的结果即可。

形式化地，对于置换 $\pi$，令 $\nu\left(\pi\right)$ 表示其不动点个数，设 $\upsilon\left(\pi\right)$ 为其能够被分解成为的最少个数对换乘积的对换数目。设 $n$ 元对称群为 $S_n$，$n$ 元交错群为 $A_n$，求

$$2\sum_{\pi\in S_n\land\pi\notin A_n}\frac{\upsilon\left(\pi\right)}{\nu\left(\pi\right)+1}. $$

这一定是一个非负整数。答案对质数 $p$ 取模后输出。

输入格式

输入一行两个正整数 $n,p$。

输出格式

输出一行一个非负整数，表示所有可能的 $n$ 道题的模拟赛的可爱程度之和对 $p$ 取模后的结果。

4 16777259

40

10 2147483647

17167120

10000000 998244353

3414058

提示

样例解释 #1

四道题的所有可能的模拟赛题目排列顺序有：

• $\left\{1,2,4,3\right\}$，可爱程度为 $1/3$；
• $\left\{1,3,2,4\right\}$，可爱程度为 $1/3$；
• $\left\{1,4,3,2\right\}$，可爱程度为 $1/3$；
• $\left\{2,1,3,4\right\}$，可爱程度为 $1/3$；
• $\left\{2,3,4,1\right\}$，可爱程度为 $3$；
• $\left\{2,4,1,3\right\}$，可爱程度为 $3$；
• $\left\{3,1,4,2\right\}$，可爱程度为 $3$；
• $\left\{3,2,1,4\right\}$，可爱程度为 $1/3$；
• $\left\{3,4,2,1\right\}$，可爱程度为 $3$；
• $\left\{4,1,2,3\right\}$，可爱程度为 $3$；
• $\left\{4,2,3,1\right\}$，可爱程度为 $1/3$；
• $\left\{4,3,1,2\right\}$，可爱程度为 $3$。

测试点约束

本题采用捆绑测试。

对于全部数据，有 $1\le n\le2\times10^7$，$2^{25}<p<2^{31}$，$p$ 为质数。

每个子任务的具体限制见下表：

子任务编号	分值	$n\le$	$p=998244353$
1	10	$2\times10^1$	$\times$
2		$2\times10^2$	$\surd$
3		$2\times10^3$	$\times$
4	20	$2\times10^4$
5		$2\times10^5$	$\surd$
6	10	$2\times10^6$
7	20	$2\times10^7$	$\times$

更快的取模

本题中你可能会执行大量取模操作，因此你可以参考几种取模优化方法（译自 min-25 的博客）来提高取模运算的效率。