#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = 900000011ll;
void read()
{
	freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
}
ll i,j,p,q,n,m,k,c;
struct Matrix
{
    int n,m;
    ll a[4][4];
};
ll pr(ll a,ll b)
{
    ll sum = 0;
    bool fl = 0;
    if(a>0 && b<0)
        fl = 1;
    if(a<0 && b>0)
        fl = 1;
    a = abs(a);
    b = abs(b);
    while(b>0)
    {
        if(b&1)
            sum=(sum+a)%mod;
        a = (a+a)%mod;
        b>>=1;
    }
    if(fl)sum=-sum;
    //cout<<a<<" "<<b<<" "<<sum<<endl;
    return sum;
}
Matrix mul(Matrix a,Matrix b)
{
    Matrix product;
    int N = a.m;
    product.n=a.n;
    product.m = b.m;
    for(int i=0; i<product.n; i++)
    {
        for(int j=0; j<product.m; j++)
        {
            product.a[i][j]=0;
            for(int k=0; k<N; k++)
            {
                product.a[i][j]+=pr(a.a[i][k],b.a[k][j]);
                product.a[i][j]%=mod;
            }
        }
    }
    return product;
}

Matrix exp(Matrix a,ll st)
{
    Matrix f;
    f.n=a.n;
    f.m = a.m;
    memset(f.a,0,sizeof(f.a));
    for(int jj=0;jj<f.n;jj++)
        f.a[jj][jj]=1ll;
    while(st>0)
    {
        if(st&1ll)
            f=mul(f,a);
        a=mul(a,a);
        st>>=1ll;
    }
    return f;
}
int main()
{
    read();
    scanf("%lld %lld",&n,&c);
    c%=mod;
    Matrix mat;
    mat.n = 3;
    mat.m = 3;
    mat.a[0][0] = c;
    mat.a[1][0] = -1;
    mat.a[2][0] = 0;

    mat.a[0][1] = 1;
    mat.a[1][1] = 0;
    mat.a[2][1] = 0;

    mat.a[0][2] = 1;
    mat.a[1][2] = 0;
    mat.a[2][2] = 1;

    mat = exp(mat,n);

    Matrix dp;
    dp.n = 1;
    dp.m = 3;
    dp.a[0][0] = c;
    dp.a[0][1] = 2;
    dp.a[0][2] = 1;


    dp = mul(dp,mat);

    /*
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
            cout<<mat.a[i][j]<<" ";
        cout<<endl;
    }



    for(i=0;i<3;i++)
        cout<<dp.a[0][i]<<" ";
    cout<<endl;
    */
    while(dp.a[0][2]<0)
        dp.a[0][2]+=mod;
    cout<<dp.a[0][2]<<endl;
	return 0;
}