/*
    題意：一個數(shù)塔，每個點的值等于左右2個兒子之和
           現(xiàn)給出頂點的值，還有底層的大小，問組成的方法數(shù)目
           最底層有baseLength<=1,000,000個正整數(shù)，數(shù)的個數(shù)按層遞減，頂點top<=1,000,000
    
    “首先顯然可以知道的是當最底層被確定的話就可以確定一個數(shù)字金字塔，也就是每個數(shù)字金字塔可以
    用他的最底層來唯一確定。    那么，求數(shù)字金字塔的個數(shù)就可以轉(zhuǎn)換為求最底層的baseLength個數(shù)的不同組合個數(shù)。”

    設最底層的為 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
    所以方案數(shù)就等于解(X0,X1,Xn)的個數(shù)(Xi>=1)
    由于Xi>=1, 所以top>=2^n 而top只有10^6，所以n小于20，超過的方案數(shù)為0
    設Yi=Xi-1，    則上面的變?yōu)?br>    top-2^n = C(n,0)Y0 + C(n,1)Y1 +   + C(n,n)Yn  (Yi>=0)
    所以上式解(Y0,Y1,Yn)的個數(shù)就是
    “多重背包，容量top - 2^n，有(n+1)個物品每個物品的容量為C(n,i)，問使背包放滿的方案個數(shù)。”
    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;
}