#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
struct C
{
    double r,i;
    C(double a=0,double b=0) {r=a;i=b;}
    C operator + (C a) {return C(r+a.r,i+a.i);}
    C operator - (C a) {return C(r-a.r,i-a.i);}
    C operator * (C a) {return C(r*a.r-i*a.i,a.r*i+a.i*r);}
    void clear() {r=0;i=0;}
};
const double PI=acos(-1);
const int N=4096;
 
int f[4096+10][4096+10];
C a[4096+10],b[4096+10];
 
int rev[4096+10];
int n,h,mo,T;
 
inline void FFT(C a[],int type)
{
    for(int i=0;i<N;i++) if(rev[i]<i) swap(a[i],a[rev[i]]);
    for(int i=2;i<=N;i<<=1)
    {
        C wn(cos(2*PI/i),type*sin(2*PI/i));
        for(int j=0;j<N;j+=i)
        {
            C t,w(1,0);
            for(int k=0;k<i/2;k++)
            {
                t=a[j+i/2+k]*w;
                a[j+i/2+k]=a[j+k]-t;
                a[j+k]=a[j+k]+t;
                w=w*wn;
            }
        }
    }
}
 
void init()
{
    for(int i=0;i<4096;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<11);
    f[0][0]=1;f[0][1]=1;
    for(int i=0;i<=1200;i++)
    {// cout<<i<<endl;
        for(int j=0;j<4096;j++) a[j].clear(),b[j].clear();
    //  memset(a,0,sizeof(a));
    //  memset(b,0,sizeof(b));
        for(int j=0;j<=1200;j++) a[j].r=b[j].r=f[i][j];
 
        FFT(a,1);FFT(b,1);
        for(int j=0;j<4096;j++) a[j]=a[j]*b[j];
        FFT(a,-1);
 
        for(int j=1;j<=1200;j++) f[i+1][j]=((int)(a[j-1].r/4096+0.5))%mo;f[i+1][0]=1;
    }
}
 
inline void read(int &x)
{
    x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while('0'<=c&&c<='9') x=x*10+c-'0',c=getchar();
}
 
int main()
{
//  freopen("a.in","r",stdin);
    cin >>T >>mo;
    init();
    while(T--)
    {
        read(n);read(h);
        printf("%d\n",(f[h][n]-f[h-1][n]+mo)%mo);
    }
    return 0;
}

设f[i][j]表示深度为i，节点数为j的二叉树个数
g[i][j]表示深度不超过i，节点数位j的二叉树个数
那么可以列出dp方程
f[i][j]=sigma(f[i-1][k]*g[i-2][j-k-1]*2+f[i-1][k]*f[i-1][j-k-1]))
g[i][j]=g[i-1][j]+f[i][j]

那么在O(n^3)就可以预处理出所有的f[i][j]值
然后对于每个询问查表输出答案

但是这样的话在100%数据下会超时

再观察dp方程，发现是个卷积的形式

那么就可以用FFT优化dp方程了
总时间复杂度O(n^2log n+T)

由于输入数据很大，所以要使用读入优化