/*
    题意：一个数塔，每个点的值等于左右2个儿子之和
           现给出顶点的值，还有底层的大小，问组成的方法数目
           最底层有baseLength<=1,000,000个正整数，数的个数按层递减，顶点top<=1,000,000
    
    “首先显然可以知道的是当最底层被确定的话就可以确定一个数字金字塔，也就是每个数字金字塔可以
    用他的最底层来唯一确定。    那么，求数字金字塔的个数就可以转换为求最底层的baseLength个数的不同组合个数。”

    设最底层的为 X0 X1  X2  Xn
    推出上一层为 X0+X1  X1+X2  Xn-1+Xn
                 X0+2X1+X2  Xn-2+2Xn-1+Xn
    top    =       C(n,0)X0 + C(n,1)X1 +   + C(n,n)Xn
    所以方案数就等于解(X0,X1,Xn)的个数(Xi>=1)
    由于Xi>=1, 所以top>=2^n 而top只有10^6，所以n小于20，超过的方案数为0
    设Yi=Xi-1，    则上面的变为
    top-2^n = C(n,0)Y0 + C(n,1)Y1 +   + C(n,n)Yn  (Yi>=0)
    所以上式解(Y0,Y1,Yn)的个数就是
    “多重背包，容量top - 2^n，有(n+1)个物品每个物品的容量为C(n,i)，问使背包放满的方案个数。”
    dp[i][j] = dp[i-1][j] + dp[i-1][j-C(n,i)]

    http://hi.baidu.com/matrush/blog/item/2ed3b3110b65190f5baf5359.html
*/
#include<cstdio>
#include<cstring>

int C[25][25];
int dp[1000010];

void init()
{
    for(int i=0;i<=20;i++)
        C[i][0]=C[i][i]=1;
    for(int i=2;i<=20;i++)
        for(int j=1;j<i;j++)
        {
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
}
int main()
{
    init();
    int n,top;
    while(~scanf("%d%d",&n,&top))
    {
        n--;
        if(n>=20||top<(1<<n)){puts("0");continue;}
        top-=(1<<n);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<=n;i++)
            for(int j=0;j+C[n][i]<=top;j++)
            {
                dp[j+C[n][i]]+=dp[j];
                if(dp[j+C[n][i]]>=1000000009)dp[j+C[n][i]]-=1000000009;
            }
        printf("%d\n",dp[top]);
    }
    return 0;
}