#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[77000000]; void *mem = memarr;
#define MD 1000000007

ull pw(ull a, ull b, ull m){ull r=1;while(b){if(b&1)r=r*a%m;b>>=1;a=a*a%m;}return r;}
int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}
int numberOfLeadingZeros(ull x){int r=56;unsigned l=x,h=x>>32;static int t[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};if(h)r-=32,l=h;if(l&0xffff0000U)r-=16,l>>=16;if(l&0x0000ff00U)r-=8,l>>=8;return r+t[l];}
ull mulmod(ull x, ull y, ull m){int k,p=2;ull i,j,c,f,l,h,d,e,a,q,r,b=0xffffffffULL;if(m<=q)return x*y%m;i=x&b;j=x>>32;c=y&b;f=y>>32;h=j*f;l=i*c;a=(l>>32)+j*c;h+=a>>32;a&=b;a+=i*f;h+=a>>32;l=l&b|(a&b)<<32;k=numberOfLeadingZeros(m);h=h<<k|l>>(64-k);l<<=k;m<<=k;d=m>>32;e=m&b;while(p--){r=h/d*e;h=h%d<<32|l>>32;l=(l&b)<<32;if(h<r)h+=m-r;else h-=r;if(h>m)h+=m;}return h>>k;}
ll chineseRemainder(int sz, ll val[], ll md[], ll inv[], ll rmd, void *mem){int i,j;ll k,*m=(ll*)mem;rep(i,sz)m[i]=val[i];rep(i,sz)rep(j,i){k=m[i]-m[j];if(k<0)k+=md[i];m[i]=k*inv[i*sz+j]%md[i];}k=0;for(i=sz-1;i>=0;i--)k=(mulmod(md[i]%rmd,k,rmd)+m[i])%rmd;return k;}

void mfft(int n, int x[], int root, int md, void *mem){int i,j,I,J,K,s=1,p,w,v,u,a,b,c,d,A,B,C,D,*y=(int*)mem;p=pw(root,(md-1)/4*3,md);root=pw(root,(md-1)/n,md);while(n>2){I=n/4;J=I+I;K=I+J;w=1;rep(i,I){v=(ll)w*w%md;u=(ll)w*v%md;rep(j,s){a=x[j+s*i];b=x[j+s*(i+I)];c=x[j+s*(i+J)];d=x[j+s*(i+K)];A=a+c;if(A>=md)A-=md;B=a-c;if(B<0)B+=md;C=b+d;if(C>=md)C-=md;D=b-d;if(D<0)D+=md;D=(ll)D*p%md;y[j+s*4*i]=A+C;y[j+s*(4*i+1)]=(ll)w*(B-D)%md;y[j+s*(4*i+2)]=(ll)v*(A-C)%md;y[j+s*(4*i+3)]=(ll)u*(B+D)%md;if(y[j+s*4*i]>=md)y[j+s*4*i]-=md;if(y[j+s*(4*i+1)]<0)y[j+s*(4*i+1)]+=md;if(y[j+s*(4*i+2)]<0)y[j+s*(4*i+2)]+=md;}w = (ll)w*root%md;}n/=4;s*=4;root=(ll)root*root%md;root=(ll)root*root%md;swap(x,y);}if(n==2){rep(i,s){y[i]=x[i]+x[i+s];if(y[i]>=md)y[i]-=md;y[i+s]=x[i]-x[i+s];if(y[i+s]<0)y[i+s]+=md;}n/=2;s*=2;root=(ll)root*root%md;swap(x,y);}rep(i,s)y[i]=x[i];}
void mfftinv(int n, int x[], int root, int md, void *mem){int i,j,I,J,K,s=1,p,w,v,u,a,b,c,d,A,B,C,D,*y=(int*)mem;root=get_inv(root,md);p=pw(root,(md-1)/4,md);root=pw(root,(md-1)/n,md);while(n>2){I=n/4;J=I+I;K=I+J;w=1;rep(i,I){v=(ll)w*w%md;u=(ll)w*v%md;rep(j,s){a=x[j+s*i];b=x[j+s*(i+I)];c=x[j+s*(i+J)];d=x[j+s*(i+K)];A=a+c;if(A>=md)A-=md;B=a-c;if(B<0)B+=md;C=b+d;if(C>=md)C-=md;D=b-d;if(D<0)D+=md;D=(ll)D*p%md;y[j+s*4*i]=A+C;y[j+s*(4*i+1)]=(ll)w*(B+D)%md;y[j+s*(4*i+2)]=(ll)v*(A-C)%md;y[j+s*(4*i+3)]=(ll)u*(B-D)%md;if(y[j+s*4*i]>=md)y[j+s*4*i]-=md;if(y[j+s*(4*i+2)]<0)y[j+s*(4*i+2)]+=md;if(y[j+s*(4*i+3)]<0)y[j+s*(4*i+3)]+=md;}w=(ll)w*root%md;}n/=4;s*=4;root=(ll)root*root%md;root=(ll)root*root%md;swap(x,y);}if(n==2){rep(i,s){y[i]=x[i]+x[i+s];if(y[i]>=md)y[i]-=md;y[i+s]=x[i]-x[i+s];if(y[i+s]<0)y[i+s]+=md;}n/=2;s*=2;root=(ll)root*root%md;swap(x,y);}rep(i,s)y[i]=x[i];}
void gmodcomvolutionsGetData(int num, ll md[], ll root[], ll inv[]){int i,j,k;static ll 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 ordered=1){int i,j,n,k,r,**a;ll*M,*R,*I,*V;V=(ll*)mem;M=V+num;R=M+num;I=R+num;gmodcomvolutionsGetData(num,M,R,I);n=max(As+Bs,Rs);for(k=1;k<n;k*=2);a=(int**)(I+num*num);a[0]=(int*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+k;mem=a[num]+k;rep(j,num){if(ordered&&M[j]>=md){rep(i,As)a[j][i]=A[i];rep(i,Bs)a[num][i]=B[i];}else{rep(i,As){a[j][i]=A[i]%M[j];if(a[j][i]<0)a[j][i]+=M[j];}rep(i,Bs){a[num][i]=B[i]%M[j];if(a[num][i]<0)a[num][i]+=M[j];}}REP(i,As,k)a[j][i]=0;REP(i,Bs,k)a[num][i]=0;mfft(k,a[j],R[j],M[j],mem);mfft(k,a[num],R[j],M[j],mem);rep(i,k)a[j][i]=(ll)a[j][i]*a[num][i]%M[j];r=get_inv(k,M[j]);mfftinv(k,a[j],R[j],M[j],mem);rep(i,Rs)a[j][i]=(ll)a[j][i]*r%M[j];}rep(i,Rs){rep(j,num)V[j]=a[j][i];res[i]=chineseRemainder(num,V,M,I,md,mem);}}
template<class S, class T> void gmodconvolution(S A[], int As, T res[], int Rs, void *mem, int md, int num=3, int ordered=1){int i,j,n,k,r,**a;ll*M,*R,*I,*V;V=(ll*)mem;M=V+num;R=M+num;I=R+num;gmodcomvolutionsGetData(num,M,R,I);n=max(As+As,Rs);for(k=1;k<n;k*=2);a=(int**)(I+num*num);a[0]=(int*)(a+num);REP(i,1,num)a[i]=a[i-1]+k;mem=a[num-1]+k;rep(j,num){if(ordered&&M[j]>=md)rep(i,As)a[j][i]=A[i];else rep(i,As){a[j][i]=A[i]%M[j];if(a[j][i]<0)a[j][i]+=M[j];}REP(i,As,k)a[j][i]=0;mfft(k,a[j],R[j],M[j],mem);rep(i,k)a[j][i]=(ll)a[j][i]*a[j][i]%M[j];r=get_inv(k,M[j]);mfftinv(k,a[j],R[j],M[j],mem);rep(i,Rs)a[j][i]=(ll)a[j][i]*r%M[j];}rep(i,Rs){rep(j,num)V[j]=a[j][i];res[i]=chineseRemainder(num,V,M,I,md,mem);}}
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 S, class T> void gmodconvolutionPreCalc(S A[], int As, T res[], int Rs, void *mem, int md, int num=3, int ordered=1, int domultiply=1){int i,j,k,r,*a;ll*M,*R,*I,*V;V=(ll*)mem;M=V+num;R=M+num;I=R+num;gmodcomvolutionsGetData(num,M,R,I);k=Rs;a=(int*)(I+num*num);mem=a+k;rep(j,num){if(ordered&&M[j]>=md)rep(i,As)a[i]=A[i];else rep(i,As){a[i]=A[i]%M[j];if(a[i]<0)a[i]+=M[j];}REP(i,As,k)a[i]=0;mfft(k,a,R[j],M[j],mem);rep(i,Rs)res[j*Rs+i]=a[i];if(domultiply){r=get_inv(k,M[j]);rep(i,Rs)res[j*Rs+i]=(ll)res[j*Rs+i]*r%M[j];}}}
template<class S, class T, class U> void gmodconvolutionWithPreCalc(S 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,k,r,**a;ll*M,*R,*I,*V;V=(ll*)mem;M=V+num;R=M+num;I=R+num;gmodcomvolutionsGetData(num,M,R,I);k=As;a=(int**)(I+num*num);a[0]=(int*)(a+num+1);REP(i,1,num+1)a[i]=a[i-1]+k;mem=a[num]+k;rep(j,num){rep(i,k)a[j][i]=A[j*k+i];if(ordered&&M[j]>=md)rep(i,Bs)a[num][i]=B[i];else rep(i,Bs){a[num][i]=B[i]%M[j];if(a[num][i]<0)a[num][i]+=M[j];}REP(i,Bs,k)a[num][i]=0;mfft(k,a[num],R[j],M[j],mem);rep(i,k)a[j][i]=(ll)a[j][i]*a[num][i]%M[j];mfftinv(k,a[j],R[j],M[j],mem);if(domultiply){r=get_inv(k,M[j]);rep(i,Rs)a[j][i]=(ll)a[j][i]*r%M[j];}}rep(i,Rs){rep(j,num)V[j]=a[j][i];res[i]=chineseRemainder(num,V,M,I,md,mem);}}

template<class T> void Kitamasa_g_reduce(int a[], int e, T c[], int d, int md, ll l, int g, int z, int **p, int *u, int *v, void *mem){int i,j,q,L,x,*D=(int*)mem;ll*Z=(ll*)(D+2*d);mem=Z+e;rep(i,e)Z[i]=a[i];for(j=z-1;j>=0;j--){x=e-d;L=u[j]-d;if(x<2*L)continue;q=x-2*L;gmodconvolutionWithPreCalc(p[j],v[j],Z+e-L,L,D,d+L,mem,md,g);rep(i,d+L){Z[q+i+1]+=D[i];if(Z[q+i]>=MD)Z[q+i]-=md;}e-=L;}while(e>d){e--;if(Z[e]>=md)Z[e]%=md;rep(i,d){Z[e-d+i]+=Z[e]*c[i];if(Z[e-d+i]>=l)Z[e-d+i]%=md;}}rep(i,e){if(Z[i]>=md)Z[i]%=md;}rep(i,e)a[i]=Z[i];}
template<class S, class T> ll Kitamasa_g(ll n, S a[], T c[], int d, int md, void *mem){int i,j,m,L,q,e,s,*A,*D,*E,R=0,*U,*V,**P,g;ll*Z,C,l=((1ULL<<63)-1)-(ull)(md-1)*(md-1);if(n<d)return a[n];g=ceil((log(2)+log(d)+2*log(md))/log(1004535809)+1e-5);U=(int*)mem;V=U+25;P=(int**)(V+25);A=(int*)(P+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_g_reduce(A,m,c,d,md,l,g,R,P,U,V,mem);U[R]=m;L=m-d;V[R]=modconvolutionGetLength(d,L,d+L);P[R]=(int*)mem;mem=P[R]+V[R]*g;gmodconvolutionPreCalc(A,d,P[R],V[R],mem,md,g);R++;}Z=(ll*)mem;e=0;for(;;){Z[e++]=n;if(n<2*d)break;n/=2;}D=(int*)(Z+e);E=D+4*d;mem=E+2*d;rep(i,2*d)A[i]=0;A[Z[--e]]=1;while(e--){gmodconvolution(A,2*d,D,4*d,mem,md,g);s=4*d;j=R-1;rep(m,2){L=U[j]-d;q=s-d-2*L;gmodconvolutionWithPreCalc(P[j],V[j],D+s-L,L,E,d+L,mem,md,g);rep(i,d+L){D[q+i+1]+=E[i];if(D[q+i]>=md)D[q+i]-=md;}s-=L;}rep(i,2*d)A[i]=D[i];if(Z[e]!=Z[e+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]+c[i]*C)%md;}}Kitamasa_g_reduce(A,2*d,c,d,md,l,g,R,P,U,V,mem);C=0;rep(i,d){C+=(ll)a[i]*A[i];if(C>=l)C%=md;}if(C>=md)C%=md;return C;}

template<class S, class T> ll Kitamasa(ll n, S a[], T c[], int d, int md, void *mem){int i,j,sz;ll*t,*A,*D,C,l=((1ULL<<63)-1)-(ull)(md-1)*(md-1);sz=0;t=(ll*)mem;for(;;){t[sz++]=n;if(n<d)break;n/=2;}A=t+sz;D=A+d;rep(i,d)A[i]=0;A[t[--sz]]=1;while(sz--){rep(i,2*d-1)D[i]=0;rep(i,d)rep(j,d){D[i+j]+=A[i]*A[j];if(D[i+j]>=l||D[i+j]<=-l)D[i+j]%=md;}for(i=2*d-2;i>=d;i--){if(D[i]>=md||D[i]<=-md)D[i]%=md;rep(j,d){D[i-d+j]+=D[i]*c[j];if(D[i-d+j]>=l||D[i-d+j]<=-l)D[i-d+j]%=md;}}rep(i,d){A[i]=D[i];if(A[i]>=md||A[i]<=-md)A[i]%=md;}if(t[sz]!=t[sz+1]*2){C=A[d-1];for(i=d-1;i;i--)A[i]=A[i-1];A[0]=0;rep(i,d){A[i]+=c[i]*C;if(A[i]<-md||A[i]>=md)A[i]%=md;}}}C=0;rep(i,d){C+=a[i]*A[i];if(C>=l||C<=-l)C%=md;}if(C<=-md||C>=md)C%=md;if(C<0)C+=md;return C;}

ll N;
int A[20000], C[20000];

int main(){
  int i, j, k, d = 7500;

  rep(i,d) A[i] = rand()%MD;
  rep(i,d) C[i] = rand()%MD;
  N = (1LL<<62)-1;

  i = Kitamasa_g(N, A, C, d, MD, mem);
  puts("dummy");

  return 0;
}