#P18512. DFS Order 4

DFS Order 4

DFS Order 4

Little Cyan Fish(也叫 Qingyu Xiao)喜欢 DFS 序。给定一棵有 n 个顶点的有根树 T,顶点编号为 1 到 n,根为顶点1。对每个 i(2≤i≤n),其父亲为 f_i,满足 1≤f_i<i。

DFS 序 D=(D_1,D_2,…,D_n) 是对这棵树进行深度优先搜索时,第一次访问各顶点的顺序。第 j 项的顶点在另外 j−1 个顶点之后被访问。每当一个顶点有多个儿子,必须按儿子编号递增的顺序依次访问。因此每棵有根树在本题中只有一个 DFS 序。

原题中的七个顶点树

上图的 DFS 序为 [1,2,3,7,4,5,6]。下面的伪代码给出了原题的生成过程,树由数组 f={f_2,…,f_n} 唯一确定。

过程 dfs(x):
    把 x 加入 dfs_order 的末尾
    按编号递增顺序,枚举 x 的每一个儿子 y:
        dfs(y)

过程 generate():
    创建全局空列表 dfs_order
    dfs(1)
    返回 dfs_order

设 D 是 generate() 的返回值。共有 (n−1)! 种不同的父数组 f,每种表示一棵不同的树。考虑所有这些父数组,一共能得到多少个不同的 DFS 序?当且仅当某个位置 i 上 D_i 与 D'_i 不同,才认为两个 DFS 序不同。不同的树可能得到同一个 DFS 序,只计一次。

给定一个质数 P,请输出这个数量对 P 取模的结果。

输入格式

只有一行,包含两个整数 n,P,其中

  • 1≤n≤800;
  • 10^8≤P≤1.01×10^9;
  • 保证 P 是质数。

输入只有一个测试用例,没有 T。P 不一定等于 998244353,也不保证适合某个长度的 NTT。

输出格式

输出一行,一个整数,表示不同 DFS 序数量对 P 取模的结果。

原样例1

输入:

4 114514199

输出:

2

原样例2

输入:

10 998244353

输出:

11033

原样例3

输入:

100 1000000007

输出:

270904395

原说明

第一个样例只有两个不同的 DFS 序:D_1=[1,2,3,4] 和 D_2=[1,2,4,3]。它们分别可以由父数组 f_2=1,f_3=1,f_4=1 和 f_2=1,f_3=1,f_4=2 的两棵树得到。

原样例中的两棵树 T1 与 T2