#P18234. Flowers
Flowers
Flowers
Frank 喜欢数字,也喜欢花。他在纸上设计了一种“数字花”。
一个无向连通图是数字花,当且仅当它满足:
- 若图有 个顶点,则顶点编号为 。
- 图恰有 条边。除顶点 外,其他顶点的度数均不超过 。
- 与顶点 直接相邻的顶点称为关键顶点,所有关键顶点的编号两两互质。对于每个既不是关键顶点、也不是顶点 的顶点 ,设距离它最近的关键顶点为 : 的编号必须是 的编号的倍数;从 沿简单路径走向 时,路径上的顶点编号必须严格递减。
由于图连通且恰有 条边,它是一棵树;移除顶点 后,每个分支都是一条链,因此上述最近关键顶点唯一。
给定 ,求有多少种包含 个顶点的数字花。如果两图的无向边集合完全相同,则认为它们相同;否则认为它们不同。
答案可能很大,只需输出它对给定质数 取模的结果。
输入格式
本题每个输入文件只有一个测试用例。
一行两个正整数 。
数据范围:
- ;
- ;
- 保证 为质数。
输出格式
输出一个整数,表示不同数字花数量对 取模的结果。
样例 1
5 998244353
1
此时唯一的数字花如下图:

关键顶点为 ,顶点 与关键顶点 相连。
样例 2
10 998244353
4
样例 3
10000000000 998244353
889033323