#P17925. Hashing

Hashing

Hashing

题目描述

对于一棵有根树,记 sz⁡u\operatorname{sz}_u 为顶点 uu 的子树大小,son⁡u\operatorname{son}_u 为 uu 的所有孩子构成的集合。

给定任意映射 f:Z>0→Z>0f:\mathbb Z_{>0}\to\mathbb Z_{>0},递归定义哈希值:

$$h(u)=1+\sum_{v\in\operatorname{son}_u}h(v)f(\operatorname{sz}_v).$$

整棵树的哈希值是根的哈希值,单点树的哈希值为 11。这里的计算使用整数,不对任何模数取模。

若存在同一个映射 ff,使两棵有根树得到不同的哈希值,则称这两棵树可区分;若对所有映射 ff,二者哈希值均相同,则称它们不可区分。

求最多能选出多少棵恰有 nn 个顶点的有根二叉树,使选出的树两两可区分。有根二叉树指每个顶点至多有两个孩子的有根树。

只需将这个最大数量对给定的 pp 取模后输出。pp 仅用于最终计数,不用于上述哈希值的定义。

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来 TT 行,每行两个整数 n,pn,p。

输出格式

每组数据输出一行一个整数,表示答案对 pp 取模的结果。

数据范围

  • 1≤T≤1041\le T\le10^4,1≤n≤30001\le n\le3000。
  • 2≤p≤109+92\le p\le10^9+9,不保证 pp 为质数。
  • 所有测试数据的 nn 之和不超过 1000010000。

样例

8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009
1
6
207
10904
478868953
202933416
152259136
264735211