背景

经过了前两次，小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 提供。