说明

刚开始有一个三角形，每秒会出现一个点，它会等概率随机地和目前图形最外围的相邻某两个点连边。

所有点有标号，所有边都是无向边，边权为 $1$。

输入 $n$，对于每个 $k\in[4,n]$ 求出图形生长到有恰好 $k$ 个点后两点间最短路的长度的和的期望，对输入的质数 $p$ 取模。

形式化题意：

无限大的二维平面上刚开始有一个三条无向边构成的三角形，即存在点 $1,2,3$ 和边 $(1,2),(2,3),(3,1)$。接下来第 $i$ 秒：

• 等概率随机选择图形外圈（与无限远处在同一个块里）的一条无向边 $(u,v)$；
• 在该边外侧（无限远处所在的块）中建立点 $i+3$；
• 连接无向边 $(u,i+3)$ 和无向边 $(v,i+3)$；

输入 $n$，对于每个 $k\in[4,n]$ 求出 $k-3$ 秒后所有无序点对之间最短路的长度的和的期望值，对输入的质数 $p$ 取模。

输入格式

第一行两个整数 $n,p$。

输出格式

为避免输出量过大，输出一行一个整数表示 $k\in[4,n]$ 的所有答案的异或和。

4 998244353

7

10 1000000007

67634987

提示

【样例 1 解释】

此时共有三种情况：

不难发现每种情况下最短路总和都是 $1+1+1+1+1+2=7$，故期望为 $7$。

【样例 2 解释】

$k$ 从 $4$ 到 $10$ 的答案依次为：

7
13
800000027
800000038
190476238
138095302
124338708

【数据范围】

对于所有测试数据，$4\le n\le 10^6$，$1145143\le p\le 10^9+9$，保证 $p$ 是质数。

【提示】

建议选手使用这份 std 使用的快速取模模板以减小常数因子：

typedef __int128_t lll;
typedef unsigned long long ull;
struct FastMod{ull b, m;
	inline void init(ull x){b = x, m = ((lll)1 << 64) / b;}
	inline ull Mod(ull a){
		ull q = ull((lll)m * a >> 64);
		ull r = a - q * b;
		return r >= b ? r - b : r;
	}
}md;