不存在的玩家

题号：NC274888
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“……比 Enucai 还好么。”

“比 Enucai 还好。”

“可你之前明明说……”

画笔与言语一并停止了。伊娜小姐站起身，像是在确定什么似地盯着我，对上的是我假装正经的脸。最后她低下头，离开的视线里似有微嗔，嘴里哎呀哎呀地轻声嘟囔着。

小 L 在做这样一个题：

给定一个 $n$ 个点的简单有向无环图 $G$ ，保证每条边 $u\to v$ 满足 $u<v$ 。现在对每个位置 $u$ ，记 $g_u$ 表示放置一个棋子在 $u$ 位置，每次可以沿着有向边移动，不能移动则停止，该棋子最大移动次数。

输出一行 $n$ 个整数，第 $i$ 个表示 $g_i$ 。

然而小 L 由于博弈题做魔怔了，读错了题，凭空想象出了两个玩家。他看成了如下题意：

给定一个 $n$ 个点的简单有向无环图 $G$ ，保证每条边 $u\to v$ 满足 $u<v$ 。现在对每个位置 $u$ ，记 $g_u$ 表示放置一个棋子在 $u$ 位置，有两个玩家每次可以沿着有向边移动，不能移动则输，该位置的 SG 函数值。

输出一行 $n$ 个整数，第 $i$ 个表示 $g_i$ 。

小 L 对着错误的题意写完后发现通过了所有样例。现在他想知道，有多少个简单有向无环图 G（不包含重边），满足对于每条边 $u\to v$ 都有 $u<v$ ，且在上述两个题意下，输出的结果是完全相等的。

由于答案很大，你需要对输入的模数 $p$ 取模。

如果您不了解 SG 函数的定义：

定义 $\text{mex}$

\operatorname{mex}

函数的值为不属于集合

中的最小非负整数，例如 $\text{mex}(\{0,2,4\})=1$

\operatorname{mex}(\{0, 2, 4\})=1

\operatorname{mex}(\{1, 2\})=0

。

考虑有向图游戏（在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负），对于状态 $x$ 和它的所有 $k$ 个后继状态 $y_1,y_2,...,y_k$ ，定义 SG 函数为： $\text{SG}(x)=\text{mex}\{\text{SG}(y_1),\text{SG}(y_2),...,\text{SG}(y_k)\}$ 。

输入描述:

输入一行两个正整数 。

数据保证：，。

输出描述:

输出一行一个非负整数，表示答案对  取模的结果。

示例1

输入

复制

3 998244353

输出

复制

说明

除了形成一条链的图（），其余的有向无环图均满足条件。

示例2

输入

复制

6 1000000000

输出

复制

示例3

输入

复制

5000 191981000

输出

复制

149349890