/ Vijos / 题库 /

小h的妹子树三

小h的妹子树三

背景

经过了前两次,小h终于发现他只能看到妹子树,却不能吃到(雾。

描述

现在小h十分伤心,他的眼前仿佛飘过来很多的妹子树,他们各不相同,唯一的相同点就是他们都是二叉树,而且深度和节点数都是相同的。现在他想数数他能看到多少种不同的妹子树,来打发时间,但是那太多了,以至于他无法记住,于是他想对一个数P取模,你能帮帮他吗?
注意:树根的深度为0,二叉树的左右子树是有区别的。
简化版题意:给定树高和节点数,求有多少种二叉树。

格式

输入格式

本题是多组数据。
开头是两个数字T和P,表示数据组数和取模数。
一下T行,每行两个数n和h,表示树节点数和高度。

输出格式

输出共T行,每行一个小于P的整数,表示答案

样例1

样例输入1

2 233
2 1
3 2

样例输出1

2
4

限制

对于10%的数据,满足1<=n<=10,1<=h<=10,
对于40%的数据,满足1<=n<=100,1<=h<=100,
对于60%的数据,满足1<=n<=600,1<=h<=600,
对于100%的数据,满足1<=n<=1200,1<=h<=1200,1<=T<=2000000,1<=P<=1007。

提示

本题有开O2

来源

感谢 yql 提供。

信息

ID
1999
难度
9
分类
小h的妹子树 点击显示
标签
(无)
递交数
131
已通过
5
通过率
4%
上传者

相关

在下列训练计划中:

RP++分类题库