#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[127000000]; void *mem = memarr;
#define MD 1000000007



struct mint{
  static unsigned md, W, R, Rinv, mdninv, RR;
  unsigned val;

  mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}
  unsigned setmod(unsigned m){W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;}}
  unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}
  unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}
  unsigned get(){return reduce(val);}
  mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}
  mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mint operator/(mint a){return mint(*this)/=a;}
  mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}
  mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}
  mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}
  operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}
  mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}
  mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}
};
unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}
mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;}

mint mval[10000], minv[10000];
void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}

#define SSE2_M128I_ADD32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_ADD64(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_SUB32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");

#define SSE2_M128U_MUL32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pmuludq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");

#define SSE2_M128I_EQ32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pcmpeqd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_GT32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pcmpgtd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_LT32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqa %%xmm0, %%xmm1;" "movdqu %2, %%xmm2;" "pcmpgtd %%xmm2, %%xmm0;" "pcmpeqd %%xmm2, %%xmm1;" "por %%xmm1, %%xmm0;" "pcmpeqd %%xmm2, %%xmm2;" "pxor %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2");
#define SSE2_M128I_GE32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqa %%xmm0, %%xmm1;" "movdqu %2, %%xmm2;" "pcmpgtd %%xmm2, %%xmm0;" "pcmpeqd %%xmm2, %%xmm1;" "por %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2");

#define SSE2_M128I_OR(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "por %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128I_AND(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pand %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");

#define SSE2_M128I_SHIFT_R4(c,a) asm volatile("movdqu %1, %%xmm0;" "psrldq $4, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");

#define SSE2_M128I_SHUFFLE32_0020(c,a) asm volatile("movdqu %1, %%xmm0;" "pshufd $8, %%xmm0, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");
#define SSE2_M128I_SHUFFLE32_0031(c,a) asm volatile("movdqu %1, %%xmm0;" "pshufd $13, %%xmm0, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a) :"%xmm0");
#define SSE2_M128I_UNPACKLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "punpckldq %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");

#define SSE2_M128U_MULLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "movdqa %%xmm0, %%xmm2;" "movdqa %%xmm1, %%xmm3;" "psrldq $4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm1, %%xmm0;" "pmuludq %%xmm3, %%xmm2;" "pshufd $8, %%xmm0, %%xmm0;" "pshufd $8, %%xmm2, %%xmm2;" "punpckldq %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");
#define SSE4_M128U_MULLO32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "pmulld %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1");
#define SSE2_M128U_MULHI32(c,a,b) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "movdqa %%xmm0, %%xmm2;" "movdqa %%xmm1, %%xmm3;" "psrldq $4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm1, %%xmm0;" "pmuludq %%xmm3, %%xmm2;" "pshufd $13, %%xmm0, %%xmm0;" "pshufd $13, %%xmm2, %%xmm2;" "punpckldq %%xmm2, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");

#define SSE2_M128U_ADDMOD32(c,a,b,md) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %3, %%xmm1;" "movdqa %%xmm1, %%xmm2;" "movdqa %%xmm0, %%xmm3;" "pcmpeqd %%xmm0, %%xmm2;" "pcmpgtd %%xmm1, %%xmm3;" "por %%xmm3, %%xmm2;" "pxor %%xmm3, %%xmm3;" "pcmpgtd %%xmm0, %%xmm3;" "por %%xmm3, %%xmm2;" "pand %%xmm2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md) :"%xmm0", "%xmm1", "%xmm2", "%xmm3");
#define SSE2_M128U_SUBMOD32(c,a,b,md) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm1;" "psubd %%xmm1, %%xmm0;" "movdqu %3, %%xmm1;" "pxor %%xmm2, %%xmm2;" "pcmpgtd %%xmm0, %%xmm2;" "pand %%xmm2, %%xmm1;" "paddd %%xmm1, %%xmm0;" "movdqu %%xmm0, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md) :"%xmm0", "%xmm1", "%xmm2");
#define SSE4_M128U_MULMOD32M(c,a,b,md,mdninv) asm volatile("movdqu %1, %%xmm0;" "movdqu %2, %%xmm2;" "movdqa %%xmm0, %%xmm1;" "pmuludq %%xmm2, %%xmm0;" "psrldq $4, %%xmm1;" "psrldq $4, %%xmm2;" "pmuldq %%xmm2, %%xmm1;" "pshufd $8, %%xmm0, %%xmm2;" "pshufd $8, %%xmm1, %%xmm3;" "punpckldq %%xmm3, %%xmm2;" "pmulld %4, %%xmm2;" "movdqu %3, %%xmm4;" "movdqa %%xmm2, %%xmm3;" "pmuludq %%xmm4, %%xmm2;" "psrldq $4, %%xmm3;" "pmuludq %%xmm4, %%xmm3;" "paddq %%xmm0, %%xmm2;" "paddq %%xmm1, %%xmm3;" "pshufd $13, %%xmm2, %%xmm2;" "pshufd $13, %%xmm3, %%xmm3;" "punpckldq %%xmm3, %%xmm2;" "movdqa %%xmm4, %%xmm3;" "movdqa %%xmm2, %%xmm0;" "pcmpeqd %%xmm0, %%xmm3;" "pcmpgtd %%xmm4, %%xmm0;" "por %%xmm3, %%xmm0;" "pxor %%xmm3, %%xmm3;" "pcmpgtd %%xmm2, %%xmm3;" "por %%xmm3, %%xmm0;" "pand %%xmm4, %%xmm0;" "psubd %%xmm0, %%xmm2;" "movdqu %%xmm2, %0;" :"=m"(c) :"m"(a), "m"(b), "m"(md), "m"(mdninv) :"%xmm0", "%xmm1", "%xmm2", "%xmm3", "%xmm4");


#define TO_MY128(a) (*(MY128*)(a))

union MY128{
  int M32I[4];
  unsigned M32U[4];
  MY128(){
  }
  MY128(int a, int b, int c, int d){
    M32I[0] = a;
    M32I[1] = b;
    M32I[2] = c;
    M32I[3] = d;
  }
  MY128(unsigned a, unsigned b, unsigned c, unsigned d){
    M32U[0] = a;
    M32U[1] = b;
    M32U[2] = c;
    M32U[3] = d;
  }
  MY128(int a){
    M32I[0] = a;
    M32I[1] = a;
    M32I[2] = a;
    M32I[3] = a;
  }
  MY128(unsigned a){
    M32U[0] = a;
    M32U[1] = a;
    M32U[2] = a;
    M32U[3] = a;
  }
  MY128(MY128 *mem){
    __asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(*mem));
  }

  void set(int a, int b, int c, int d){
    M32I[0] = a;
    M32I[1] = b;
    M32I[2] = c;
    M32I[3] = d;
  }
  void set(unsigned a, unsigned b, unsigned c, unsigned d){
    M32U[0] = a;
    M32U[1] = b;
    M32U[2] = c;
    M32U[3] = d;
  }
  void set(int a){
    M32I[0] = a;
    M32I[1] = a;
    M32I[2] = a;
    M32I[3] = a;
  }
  void set(unsigned a){
    M32U[0] = a;
    M32U[1] = a;
    M32U[2] = a;
    M32U[3] = a;
  }
  void set(MY128 *mem){
    __asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(*mem));
  }
  void get(MY128 *mem){
    __asm__ volatile("movdqu %1, %0;" :"=m"(*mem) :"m"(*this));
  }

  MY128& operator=(MY128 a){
    __asm__ volatile("movdqu %1, %0;" :"=m"(*this) :"m"(a));
    return *this;
  }
} __attribute__((aligned(16)));


void mfft(int n, mint x[], mint root, void *mem){
  int i, j, k;
  int n1, n2, n3, step = 1;
  mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
  MY128 A, B, C, D, AA, BB, CC, DD, md, t1, t2, mask, TMP, W1, W2, W3, MDNINV;
  MY128 *tt;

  tmp = root.pw((mint::md-1)/4*3);
  root = root.pw((mint::md-1)/n);

  md.set(mint::md);
  TMP.set(tmp.val);
  MDNINV.set(mint::mdninv);

  while(n > 2){
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    w1.val = mint::R;
    rep(i,n1){
      w2 = w1*w1;
      w3 = w1*w2;
      W1.set(w1.val);
      W2.set(w2.val);
      W3.set(w3.val);
      for(j=0;j+3<step;j+=4){
        SSE2_M128U_ADDMOD32(AA, x[j+step*i], x[j+step*(i+n2)], md);
        SSE2_M128U_SUBMOD32(BB, x[j+step*i], x[j+step*(i+n2)], md);
        SSE2_M128U_ADDMOD32(CC, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
        SSE2_M128U_SUBMOD32(DD, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
        SSE4_M128U_MULMOD32M(DD, DD, TMP, md, MDNINV);

        SSE2_M128U_ADDMOD32(y[j+step*(4*i  )], AA, CC, md);
        SSE2_M128U_SUBMOD32(B, BB, DD, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+1)], W1, B, md, MDNINV);
        SSE2_M128U_SUBMOD32(C, AA, CC, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+2)], W2, C, md, MDNINV);
        SSE2_M128U_ADDMOD32(D, BB, DD, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+3)], W3, D, md, MDNINV);
      }
      REP(j,j,step){
        a = x[j+step*i];
        b = x[j+step*(i+n1)];
        c = x[j+step*(i+n2)];
        d = x[j+step*(i+n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = (b - d) * tmp;
        y[j+step*(4*i  )] = aa + cc;
        y[j+step*(4*i+1)] = w1*(bb - dd);
        y[j+step*(4*i+2)] = w2*(aa - cc);
        y[j+step*(4*i+3)] = w3*(bb + dd);
      }
      w1 *= root;
    }
    n /= 4;
    step *= 4;
    root *= root;
    root *= root;
    swap(x,y);
  }

  if(n==2){
    for(i=0;i+3<step;i+=4){
      SSE2_M128U_ADDMOD32(y[i], x[i], x[i+step], md);
      SSE2_M128U_SUBMOD32(y[i+step], x[i], x[i+step], md);
    }
    REP(i,i,step){
      y[i] = x[i] + x[i+step];
      y[i+step] = x[i] - x[i+step];
    }
    n /= 2;
    step *= 2;
    root *= root;
    swap(x,y);
  }
  
  rep(i,step) y[i] = x[i];
}



void mfftinv(int n, mint x[], mint root, void *mem){
  int i, j;
  int n1, n2, n3, step = 1;
  mint w1, w2, w3, a, b, c, d, aa, bb, cc, dd, tmp, *y = (mint*)mem;
  MY128 A, B, C, D, AA, BB, CC, DD, md, t1, t2, mask, TMP, W1, W2, W3, MDNINV;

  root = root.inverse();
  tmp = root.pw((mint::md-1)/4);
  root = root.pw((mint::md-1)/n);

  md.set(mint::md);
  TMP.set(tmp.val);
  MDNINV.set(mint::mdninv);

  while(n > 2){
    n1 = n / 4;
    n2 = n1 + n1;
    n3 = n1 + n2;
    w1.val = mint::R;
    rep(i,n1){
      w2 = w1*w1;
      w3 = w1*w2;
      W1.set(w1.val);
      W2.set(w2.val);
      W3.set(w3.val);
      for(j=0;j+3<step;j+=4){
        SSE2_M128U_ADDMOD32(AA, x[j+step*i], x[j+step*(i+n2)], md);
        SSE2_M128U_SUBMOD32(BB, x[j+step*i], x[j+step*(i+n2)], md);
        SSE2_M128U_ADDMOD32(CC, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
        SSE2_M128U_SUBMOD32(DD, x[j+step*(i+n1)], x[j+step*(i+n3)], md);
        SSE4_M128U_MULMOD32M(DD, DD, TMP, md, MDNINV);

        SSE2_M128U_ADDMOD32(y[j+step*(4*i  )], AA, CC, md);
        SSE2_M128U_ADDMOD32(B, BB, DD, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+1)], W1, B, md, MDNINV);
        SSE2_M128U_SUBMOD32(C, AA, CC, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+2)], W2, C, md, MDNINV);
        SSE2_M128U_SUBMOD32(D, BB, DD, md);
        SSE4_M128U_MULMOD32M(y[j+step*(4*i+3)], W3, D, md, MDNINV);
      }
      REP(j,j,step){
        a = x[j+step*i];
        b = x[j+step*(i+n1)];
        c = x[j+step*(i+n2)];
        d = x[j+step*(i+n3)];
        aa = a + c;
        bb = a - c;
        cc = b + d;
        dd = (b - d) * tmp;
        y[j+step*(4*i  )] = aa + cc;
        y[j+step*(4*i+1)] = w1*(bb + dd);
        y[j+step*(4*i+2)] = w2*(aa - cc);
        y[j+step*(4*i+3)] = w3*(bb - dd);
      }
      w1 *= root;
    }
    n /= 4;
    step *= 4;
    root *= root;
    root *= root;
    swap(x,y);
  }

  if(n==2){
    for(i=0;i+3<step;i+=4){
      SSE2_M128U_ADDMOD32(y[i], x[i], x[i+step], md);
      SSE2_M128U_SUBMOD32(y[i+step], x[i], x[i+step], md);
    }
    REP(i,i,step){
      y[i] = x[i] + x[i+step];
      y[i+step] = x[i] - x[i+step];
    }
    n /= 2;
    step *= 2;
    root *= root;
    swap(x,y);
  }
  
  rep(i,step) y[i] = x[i];
}

void gmodcomvolutionsGetData(int num, int md[], int root[], int inv[]){int i,j,k;static int A[5]={1004535809,1007681537,1012924417,1045430273,1051721729},B[5]={3,3,5,3,6},C[5][5]={{},{335894166},{253231225,405169960},{26805930,551754894,843088962},{303830744,325532940,568498259,175287122}};rep(i,num)md[i]=A[i];rep(i,num)root[i]=B[i];rep(i,num)rep(j,i)inv[i*num+j]=C[i][j];}
template<class S, class T, class U> void gmodconvolution(S A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+Bs,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];rep(i,Bs)a[num][i]=B[i];REP(i,As,q)a[j][i].val=0;REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[j],R,mem);mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S, class T> void gmodconvolution(S A[], int As, T res[], int Rs, void *mem, int md, int num=3){int i,j,k,m,n,q,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);n=max(As+As,Rs);for(q=1;q<n;q*=2);a=(mint**)(z+num*num);a[0]=(mint*)(a+num);REP(i,1,num)a[i]=a[i-1]+q;mem=a[num-1]+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[j][i]=A[i];REP(i,As,q)a[j][i].val=0;R=y[j];mfft(q,a[j],R,mem);rep(i,q)a[j][i]*=a[j][i];r=mint(q).inverse();mfftinv(q,a[j],R,mem);rep(i,Rs)a[j][i]*=r;rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
template<class S> void gmodconvolutionPreCalc(S A[], int As, mint res[], int Rs, void *mem, int md, int num=3, int domultiply=1){int i,j,q,*x,*y,*z,*w;mint r,R,*a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=Rs;a=(mint*)(z+num*num);mem=a+q;rep(j,num){r.setmod(x[j]);rep(i,As)a[i]=A[i];REP(i,As,q)a[i].val=0;R=y[j];mfft(q,a,R,mem);rep(i,Rs)res[j*Rs+i]=a[i];if(domultiply){r=mint(q).inverse();rep(i,Rs)res[j*Rs+i]*=r;}}r.setmod(md);}
template<class T, class U> void gmodconvolutionWithPreCalc(mint A[], int As, T B[], int Bs, U res[], int Rs, void *mem, int md, int num=3, int ordered=1, int domultiply=0){int i,j,q,k,m,*x,*y,*z,*w;mint r,R,**a;w=(int*)mem;x=w+num;y=x+num;z=y+num;gmodcomvolutionsGetData(num,x,y,z);q=As;a=(mint**)(z+num*num);a[0]=(mint*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+q;mem=a[num]+q;rep(j,num){r.setmod(x[j]);rep(i,q)a[j][i]=A[j*q+i];rep(i,Bs)a[num][i]=B[i];REP(i,Bs,q)a[num][i].val=0;R=y[j];mfft(q,a[num],R,mem);rep(i,q)a[j][i]*=a[num][i];mfftinv(q,a[j],R,mem);if(domultiply){r=mint(q).inverse();rep(i,Rs)a[j][i]*=r;}rep(i,Rs)a[j][i].val=a[j][i].get();}r.setmod(md);rep(m,Rs){rep(i,num)w[i]=a[i][m].val;rep(i,num)rep(j,i){k=w[i]-w[j];if(k<0)k+=x[i];w[i]=(ll)k*z[i*num+j]%x[i];}k=0;for(i=num-1;i>=0;i--)k=((ll)k*x[i]+w[i])%md;res[m]=k;}}
int modconvolutionGetLength(int As, int Bs, int Rs){int n=max(As+Bs,Rs),res;for(res=1;res<n;res*=2);return res;}

template<class T> void Kitamasa_mg_reduce(int a[], int y, T c[], int d, int md, ll L, int h, int o, mint **calc, int *q, int *p, void *mem){int i,j,t,l,E,*D=(int*)mem;ll*Z=(ll*)(D+2*d);mem=(void*)(Z+y);rep(i,y)Z[i]=a[i];for(j=o-1;j>=0;j--){E=y-d;l=q[j]-d;if(E<2*l)continue;t=E-2*l;gmodconvolutionWithPreCalc(calc[j],p[j],Z+y-l,l,D,d+l,mem,md,h);rep(i,d+l){Z[t+i+1]+=D[i];if(Z[t+i]>=md)Z[t+i]-=md;}y-=l;}while(y>d){y--;if(Z[y]>=md)Z[y]%=md;rep(i,d){Z[y-d+i]+=Z[y]*(ll)c[i];if(Z[y-d+i]>=L)Z[y-d+i]%=md;}}rep(i,y)if(Z[i]>=md)Z[i]%=md;rep(i,y)a[i]=Z[i];}
template<class S, class T> ll Kitamasa_mg(ll n, S a[], T c[], int d, int md, void *mem){int i,j,m,l,t,y,s,*A,*D,*E,o=0,*R,*W,h;mint **Q;ll L=((1ULL<<63)-1)-(ull)(md-1)*(md-1),*Z,C;if(n<d)return a[n];h=ceil((log(2)+log(d)+2*log(md))/log(1004535809)+1e-5);R=(int*)mem;W=R+25;Q=(mint**)(W+25);A=(int*)(Q+25);mem=A+2*d;for(i=20;i>=0;i--)if(d/(1<<i)>=500||i==0){m=d+d/(1<<i);rep(j,m)A[j]=0;A[m-1]=1;Kitamasa_mg_reduce(A,m,c,d,md,L,h,o,Q,R,W,mem);R[o]=m;l=m-d;W[o]=modconvolutionGetLength(d,l,d+l);Q[o]=(mint*)mem;mem=Q[o]+W[o]*h;gmodconvolutionPreCalc(A,d,Q[o],W[o],mem,md,h);o++;}Z=(ll*)mem;y=0;for(;;){Z[y++]=n;if(n<2*d)break;n/=2;}D=(int*)(Z+y);E=D+4*d;mem=E+2*d;rep(i,2*d)A[i]=0;A[Z[--y]]=1;while(y--){gmodconvolution(A,2*d,D,4*d,mem,md,h);s=4*d;j=o-1;rep(m,2){l=R[j]-d;t=s-d-2*l;gmodconvolutionWithPreCalc(Q[j],W[j],D+s-l,l,E,d+l,mem,md,h);rep(i,d+l){D[t+i+1]+=E[i];if(D[t+i+1]>=md)D[t+i+1]-=md;}s-=l;}rep(i,2*d)A[i]=D[i];if(Z[y]!=Z[y+1]*2){C=A[2*d-1];for(i=2*d-1;i;i--)A[i]=A[i-1]; A[0]=0;rep(i,d)A[d+i]=(A[d+i]+(ll)c[i]*C)%md;}}Kitamasa_mg_reduce(A,2*d,c,d,md,L,h,o,Q,R,W,mem);C=0;rep(i,d){C+=(ll)a[i]*A[i];if(C>=L)C%=md;}if(C>=md)C%=md;return C;}

int pp[6] = {2,3,5,7,11,13};
int cc[6] = {4,6,8,9,10,12};

mint dp_p[301][4200], dp_c[301][4200];
mint a[9400], c[9400];
int aaa[9400], ccc[9400];

int main(){
  int i, j, k, d;
  ll N; int P, C;
  int res;

  mint_init();

  dp_p[0][0] = dp_c[0][0] = mval[1];
  rep(k,6) rep(i,300) rep(j,4200) if(dp_p[i][j]) dp_p[i+1][j+pp[k]] += dp_p[i][j];
  rep(k,6) rep(i,300) rep(j,4200) if(dp_c[i][j]) dp_c[i+1][j+cc[k]] += dp_c[i][j];

  reader(&N);
  reader(&P, &C);

  d = P * pp[5] + C * cc[5];
  rep(i,d) a[i] = mval[1];
  rep(i,4200) if(dp_p[P][i]) rep(j,4200) if(dp_c[C][j]) c[d-i-j] += dp_p[P][i] * dp_c[C][j];

  rep(i,d) aaa[i]=(int)a[i];
  rep(i,d) ccc[i]=(int)c[i];

  res = Kitamasa_mg(N+d-1, aaa, ccc, d, MD, mem);

  writer(res, '\n');


  return 0;
}