#P18234. Flowers

Flowers

Flowers

Frank 喜欢数字,也喜欢花。他在纸上设计了一种“数字花”。

一个无向连通图是数字花,当且仅当它满足:

  1. 若图有 nn 个顶点,则顶点编号为 1,2,…,n1,2,\ldots,n。
  2. 图恰有 n−1n-1 条边。除顶点 11 外,其他顶点的度数均不超过 22。
  3. 与顶点 11 直接相邻的顶点称为关键顶点,所有关键顶点的编号两两互质。对于每个既不是关键顶点、也不是顶点 11 的顶点 vv,设距离它最近的关键顶点为 kk:vv 的编号必须是 kk 的编号的倍数;从 vv 沿简单路径走向 kk 时,路径上的顶点编号必须严格递减。

由于图连通且恰有 n−1n-1 条边,它是一棵树;移除顶点 11 后,每个分支都是一条链,因此上述最近关键顶点唯一。

给定 nn,求有多少种包含 nn 个顶点的数字花。如果两图的无向边集合完全相同,则认为它们相同;否则认为它们不同。

答案可能很大,只需输出它对给定质数 pp 取模的结果。

输入格式

本题每个输入文件只有一个测试用例。

一行两个正整数 n,pn,p。

数据范围:

  • 1≤n≤10101\le n\le10^{10};
  • 108<p<10910^8<p<10^9;
  • 保证 pp 为质数。

输出格式

输出一个整数,表示不同数字花数量对 pp 取模的结果。

样例 1

5 998244353
1

此时唯一的数字花如下图:

原题样例1的数字花

关键顶点为 2,3,52,3,5,顶点 44 与关键顶点 22 相连。

样例 2

10 998244353
4

样例 3

10000000000 998244353
889033323