#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
typedef pair<int,int> pii;


const int mod=900000011;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,ll pw){int ret=1;while(pw){if(pw&1ll)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

int global_k;
ll n,c;

struct sqs{

    int a,b,k;

    sqs(){}
    sqs(int a,int b,int k){
        this->a=a;
        this->b=b;
        this->k=k;
    }

    sqs muls(sqs o){

        sqs ret;

        ret.k=k;
        ret.a=add( mul(a,o.a) , mul( k,mul(b,o.b) ) );
        ret.b=add( mul(a,o.b) , mul(b,o.a) );

        return ret;
    }

    sqs adds(sqs &o){

        sqs ret;

        ret.k=k;
        ret.a=add( a , o.a );
        ret.b=add( b , o.b );

        return ret;

    }
    sqs subs(sqs &o){

        sqs ret;

        ret.k=k;
        ret.a=sub( a , o.a );
        ret.b=sub( b , o.b );

        return ret;

    }
    sqs invs(){

        sqs ret(a,sub(0,b),k);

        int coef=invv(sub(mul(a,a),mul( k,mul(b,b) )));

        ret.a=mul(ret.a,coef);
        ret.b=mul(ret.b,coef);

        return ret;

    }

};
sqs steps(sqs base,ll pw){

    sqs ret(1,0,global_k);

    while(pw){
        if(pw&1ll)ret=ret.muls(base);
        base=base.muls(base);
        pw>>=1;
    }

    return ret;
}

void go(){

    sqs x( mul(c,invv(2)) , invv(2) , global_k);
    sqs ix=x.invs();

    sqs xm1(sub(x.a,1),x.b,x.k);
    sqs ixm1(sub(ix.a,1),ix.b,ix.k);

    n++;

    sqs part1=steps(x,n);
    part1.a=sub(part1.a,1);
    part1=part1.muls(xm1.invs());

    sqs part2=steps(ix,n);
    part2.a=sub(part2.a,1);
    part2=part2.muls(ixm1.invs());

    part1=part1.adds(part2);

    part1.a=sub(part1.a,1);

    printf("%d\n",part1.a);

}


int main(){

    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);



    /// STAVI LONG LONG U PW U STEPENOVANJU

    scanf("%lld %lld",&n,&c);

    c%=mod;
    global_k=sub(mul(c,c),4);

    /*for(int i=1;i<=1000000;i++){
        n=i;
        go();
    }*/
    go();


return 0;
}