#include<bits/stdc++.h>
#include<sys/time.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[17000000]; void *mem = memarr;
#define MD 1000000007

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;}

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);}
  void setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;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;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}}
  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;}
  bool operator==(int a){return get()==a;}
  bool operator!=(int a){return get()!=a;}
};
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;}

void mfft(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;t=root.pw((mint::md-1)/4*3);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B-D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B+D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}
void mfftinv(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;root=root.inverse();t=root.pw((mint::md-1)/4);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B+D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B-D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}

void modconvolution(mint A[], int As, mint B[], int Bs, mint res[], int Rs, void *mem, mint root){int i,n,m;mint*a,*b,r;n=max(As+Bs,Rs);for(m=1;m<n;m*=2);a=(mint*)mem;b=a+m;mem=b+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;rep(i,Bs)b[i]=B[i];REP(i,Bs,m)b[i].val=0;mfft(m,a,root,mem);mfft(m,b,root,mem);rep(i,m)a[i]*=b[i];mfftinv(m,a,root,mem);r=mint(m).inverse();rep(i,Rs)res[i]=a[i]*r;}
void modconvolution(mint A[], int As, mint res[], int Rs, void *mem, mint root){int i,n,m;mint*a,r;n=max(2*As, Rs);for(m=1;m<n;m*=2);a=(mint*)mem;mem=a+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;mfft(m,a,root,mem);rep(i,m)a[i]*=a[i];mfftinv(m,a,root,mem);r=mint(m).inverse();rep(i,Rs)res[i]=a[i]*r;}

int modconvolutionGetLength(int As, int Bs, int Rs){int n=max(As+Bs,Rs),res;for(res=1;res<n;res*=2);return res;}
void modconvolutionPreCalc(mint A[], int As, mint res[], int Rs, void *mem, int root, int domultiply=1){int i,m;mint*a,r;m=Rs;a=(mint*)mem;mem=a+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;mfft(m,a,root,mem);rep(i,Rs)res[i]=a[i];if(domultiply){r=mint(m).inverse();rep(i,Rs)res[i]*=r;}}
void modconvolutionWithPreCalc(mint A[], int As, mint B[], int Bs, mint res[], int Rs, void *mem, int root, int domultiply=0){int i,m,r;mint*a,*b;m=As;a=(mint*)mem;b=a+m;mem=b+m;rep(i,As)a[i]=A[i];rep(i,Bs)b[i]=B[i];REP(i,Bs,m)b[i].val=0;mfft(m,b,root,mem);rep(i,m)a[i]*=b[i];mfftinv(m,a,root,mem);rep(i,Rs)res[i]=a[i];if(domultiply){r=mint(m).inverse();rep(i,Rs)res[i]*=r;}}

struct bigInt{
  int sz, mem, sign;
  unsigned *d;

  static void *workMemory;
  static bigInt *writerbase;

  inline void init(void){mem=0;d=NULL;set();}
  inline void init(int x){mem=0;d=NULL;set(x);}
  inline void init(unsigned x){mem=0;d=NULL;set(x);}
  inline void init(bigInt &x){mem=0;d=NULL;set(x);}

  inline void set(void){sz=sign=0;}
  inline void set(int x){if(x==0){set();return;}sz=1;extend(sz);if(x<0)sign*=-1,d[0]=-((ll)x);else sign=1,d[0]=x;}
  inline void set(unsigned x){if(x==0){set();return;}sz=1;extend(sz);sign=1;d[0]=x;}
  inline void set(bigInt &a){int i;sz=a.sz;sign=a.sign;extend(sz);rep(i,sz)d[i]=a[i];}

  inline unsigned& operator[](int n){return d[n];}
  inline void extend(int k){if(mem<k)k=max(k+1,mem+mem/2),d=(unsigned*)realloc(d,k*sizeof(unsigned)),mem=k;  }
  inline void *malloc(int k, void *work){d=(unsigned*)work;mem=2100000000;return d+k;}

  bool operator==(bigInt &a){int i;if(sign!=a.sign||sz!=a.sz)return false;rep(i,sz) if(d[i] != a.d[i])return false;return true;}
  bool operator<(bigInt &a){if(sign<a.sign)return true;if(sign>a.sign)return false;if(sign==0)return false;if(sign*cmp(sz,d,a.sz,a.d)==-1) return true;return false;}

  inline int cmp(int as, unsigned a[], int bs, unsigned b[]){if(as>bs)return 1;if(as<bs)return-1;int i;for(i=as-1;i>=0;i--){if(a[i]>b[i])return 1;if(a[i]<b[i])return-1;}return 0;}

  inline int Lshift(int as, unsigned a[], int val, unsigned c[]){int i,s,d,r;d=val/32;r=val%32;if(r){s=as+d+1;c[s-1]=0;for(i=as-1;i>=0;i--)c[i+d+1]|=a[i]>>(32-r),c[i+d]=a[i]<<r;rep(i,d)c[i]=0;if(c[s-1]==0)s--;}else{for(i=as-1;i>=0;i--)c[i+d]=a[i];rep(i,d)c[i]=0;s=as+d;}return s;}
  inline int Rshift(int as, unsigned a[], int val, unsigned c[]){return -1;}

  inline int add(int as, unsigned a[], unsigned b, unsigned r[]){int i,s=as;rep(i,s)r[i]=a[i];rep(i,s){if(r[i]+b<r[i])r[i]+=b,b=1;else r[i]+=b,b=0;}if(b)r[s++]=b;return s;}
  inline int add(int as, unsigned a[], unsigned b){int i;rep(i,as){if(a[i]+b<a[i])a[i]+=b,b=1;else a[i]+=b,b=0;}if(b)a[as++]=b;return as;}

  inline int sub(int as, unsigned a[], unsigned b, unsigned r[]){int i,s=as;rep(i,s)r[i]=a[i];rep(i,s){if(r[i] < b)r[i]-=b,b=1;else{r[i]-=b;break;}}if(s&&r[s-1]==0)s--;return s;}
  inline int sub(int as, unsigned a[], unsigned b){int i;rep(i,as){if(a[i]<b)a[i]-=b,b=1;else{a[i]-=b;break;}}if(a[as-1]==0)as--;return as;}

  inline int add(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i,s;unsigned*c=(unsigned*)work;if(as<bs){s=bs+1;c[0]=0;rep(i,as)c[i+1]=(a[i]+b[i]<a[i])?1:0,r[i]=a[i]+b[i];REP(i,as,bs)c[i+1]=0,r[i]=b[i];r[s-1]=0;rep(i,s){if(r[i]+c[i]<r[i])c[i+1]++;r[i]+=c[i];}}else{s=as+1;c[0]=0;rep(i,bs)c[i+1]=(a[i]+b[i]<a[i])?1:0,r[i]=a[i]+b[i];REP(i,bs,as)c[i+1]=0,r[i]=a[i];r[s-1]=0;rep(i,s){if(r[i]+c[i]<r[i])c[i+1]++;r[i]+=c[i];}}if(s&&r[s-1]==0)s--;return s;}
  inline int add(int as, unsigned a[], int bs, unsigned b[]){int i;unsigned c;if(as<bs){REP(i,as,bs)a[i]=b[i];swap(bs,as);}c=0;rep(i,bs){if(c){c=0;if(a[i]==4294967295U)c=1;a[i]++;}if(a[i]+b[i]<a[i])c=1;a[i]+=b[i];}while(c){c=0;if(i==as)a[as++]=0;if(a[i]==4294967295U)c=1;a[i]++;i++;}return as;}

  inline int sub(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i,s;unsigned*c=(unsigned*)work;c[0]=0;s=as;rep(i,bs){if(a[i]<b[i])c[i+1]=1;else c[i+1]=0;r[i]=a[i]-b[i];}REP(i,bs,as)c[i+1]=0,r[i]=a[i];rep(i,as){if(r[i]<c[i])c[i+1]++;r[i]-=c[i];}while(s&&r[s-1]==0)--s;return s;}
  inline int sub(int as, unsigned a[], int bs, unsigned b[]){int i;unsigned c=0;rep(i,bs){if(c){c=0;if(a[i]==0)c=1;a[i]--;}if(a[i]<b[i])c=1;a[i]-=b[i];}while(c){c=0;if(a[i]==0)c=1;a[i]--;i++;}while(as&&a[as-1]==0)as--;return as;}

  inline int mul(int as, unsigned a[], unsigned b, unsigned r[]){int i;ull t=0;rep(i,as)t+=(ull)b*a[i],r[i]=t&0xFFFFFFFF,t>>=32;if(t)r[as++]=t;return as;}
  inline unsigned div(int as, unsigned a[], unsigned b, int &ds, unsigned d[]){int i;ull t=0;ds=as;for(i=ds-1;i>=0;i--)t=(t<<32)+a[i],d[i]=t/b,t%=b;if(ds&&d[ds-1]==0)ds--;return t;}

  inline int mulSimple(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i,j,x,y;ull s,c,t;unsigned*arr=(unsigned*)work;if(as==0||bs==0)return 0;rep(i,as)arr[i]=a[i];s=c=0;rep(i,as+bs){x=max(0,i-as+1);y=min(bs,i+1);REP(j,x,y){t=(ull)arr[i-j]*b[j];if(s+t<s)c++;s+=t;}r[i]=s&0xFFFFFFFF;s=(c<<32)+(s>>32);c=0;}as+=bs;if(r[as-1]==0)as--;return as;}
  inline int mulKaratsuba(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){int i,m,d,A,B,C,D,E,F,G,H,I,J,K,s;unsigned*x,*y,*z,*j,*k,r;double X,Y,Z;while(as&&a[as-1]==0)as--;while(bs&&b[bs-1]==0)bs--;if(as==0||bs==0)return 0;if((ll)as*bs<100)return mulSimple(as,a,bs,b,c,work);m=max(as,bs);X=1.43e-3*as*bs;Y=2.1e-2*m*pow(min(as,bs),0.6);Z=1.9e-1*m*pow(log(m),1.5);if(m>480000)Z=1e100;if(X<=Y&&X<=Z)return mulSimple(as,a,bs,b,c,work);if(Z<=X&&Z<=Y)return mulFFT8(as,a,bs,b,c,work);d=(m+1)/2;A=min(as,d);B=as-A;C=min(bs,d);D=bs-C;x=(unsigned*)work;z=x+(A+C);y=z+(B+D);j=y+(A+C+2);k=j+A;work=k+C;while(A&&a[A-1]==0)A--;while(C&&b[C-1]==0)C--;E=mulKaratsuba(A,a,C,b,x,work);G=mulKaratsuba(B,a+d,D,b+d,z,work);J=cmp(B,a+d,A,a);K=cmp(D,b+d,C,b);if(J==0||K==0)F=0,F=add(F,y,E,x),F=add(F,y,G,z);else{if(J==1)H=sub(B,a+d,A,a,j,work);else H=sub(A,a,B,a+d,j,work);if(K==1)I=sub(D,b+d,C,b,k,work);else I=sub(C,b,D,b+d,k,work);F=mulKaratsuba(H,j,I,k,y,work);if(J+K==0)F=add(F,y,E,x),F=add(F,y,G,z);else if(J==1&&K==1)F=sub(G,z,F,y,y,work),F=add(F,y,E,x);else F=sub(E,x,F,y,y,work),F=add(F,y,G,z);}s=as+bs;rep(i,E)c[i]=x[i];REP(i,E,d+d)c[i]=0;rep(i,G)c[d+d+i]=z[i];REP(i,d+d+G,s)c[i]=0;r=0;rep(i,F){if(r){r=0;if(c[i+d]==4294967295U)r=1;c[i+d]++;}if(c[i+d]+y[i]<c[i+d])r=1;c[i+d]+=y[i];}while(r){r=0;if(c[i+d]==4294967295U)r=1;c[i+d]++;i++;}if(c[s-1]==0)s--;return s;}
  inline int mulFFT8(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){int i,j,k,A,B,C,s;unsigned m,t,r,w;mint*x,*y,*z,n;A=as*8;B=bs*8;C=A+B;x=(mint*)work;y=x+A;z=y+B;work=z+C;m=mint::md;n.setmod(1004535809U);rep(i,as)rep(k,8)x[8*i+k]=mint((a[i]>>(4*k))&15U);rep(i,bs)rep(k,8)y[8*i+k]=mint((b[i]>>(4*k))&15U);modconvolution(x,A,y,B,z,C,work,mint(3U));s=as+bs;rep(i,s)c[i]=(int)z[8*i];rep(i,s){REP(k,1,8){t=(int)z[8*i+k];r=t<<(k*4);w=t>>(32-k*4);if(r)for(j=i;;j++){if(c[j]+r>=c[j]){c[j]+=r;break;}c[j]+=r;r=1;}if(w)for(j=i+1;;j++){if(c[j]+w>=c[j]){c[j]+=w;break;}c[j]+=w;w=1;}}}n.setmod(m);while(s&&c[s-1]==0)s--;return s;}

  inline void divKaratsuba(int as, unsigned a[], int bs, unsigned b[], int &ds, unsigned d[], int &rs, unsigned r[], void *work){int i,p,s,k,h,A,B,C,D,E;unsigned f,*w,*x,*t,*y,*z,*l,*m;while(as&&a[as-1]==0)as--;while(bs&&b[bs-1]==0)bs--;k=cmp(bs,b,as,a);if(k==1){ds=0;rs=as;rep(i,rs)r[i]=a[i];return;}if(bs==1){r[0]=div(as,a,b[0],ds,d);rs=1;if(!r[0])rs=0;return;}h=max(0,as+1-bs*2)+1;l=(unsigned*)work;m=l+as+h+1;work=m+bs+h;f=(1ULL<<32)/(b[bs-1]+1);as=mul(as,a,f,l);bs=mul(bs,b,f,m);h=max(0,as-bs*2);if((bs+h)%2)h++;if(h>0){for(i=as-1;i>=0;i--)l[i+h]=l[i];rep(i,h)l[i]=0;for(i=bs-1;i>=0;i--)m[i+h]=m[i];rep(i,h)m[i]=0;as+=h;bs+=h;}p=bs/2;s=max(0,as-2*p);A=max(0,s-bs+p+1);C=p+A;B=max(bs+1,C);D=B-bs+p+1;C=max(C,D+p);E=max(bs+1,C);w=(unsigned*)work;x=w+A;t=x+B;y=t+C;z=y+D;work=z+E;divKaratsuba(s,l+2*p,bs-p,m+p,A,w,B,x,work);if(B){rep(i,B)x[i+p]=x[i];rep(i,p)x[i]=0;B+=p;}s=min(p,as-p);B=add(B,x,s,l+p);C=mulKaratsuba(p,m,A,w,t,work);k=cmp(B,x,C,t);while(k==-1)A=sub(A,w,1U),B=add(B,x,bs,m),k=cmp(B,x,C,t);if(k==1)B=sub(B,x,C,t);else B=0;divKaratsuba(B,x,bs-p,m+p,D,y,E,z,work);if(E){rep(i,E)z[i+p]=z[i];rep(i,p)z[i]=0;E+=p;}E=add(E,z,p,l);C=mulKaratsuba(p,m,D,y,t,work);k=cmp(E,z,C,t);while(k==-1)D=sub(D,y,1U),E=add(E,z,bs,m),k=cmp(E,z,C,t);if(k==1)E=sub(E,z,C,t);else E=0;ds=0;if(A){ds=A+p;rep(i,A)d[i+p]=w[i];rep(i,p)d[i]=0;}ds=add(ds,d,D,y);rs=max(0,E-h);rep(i,rs)r[i]=z[i+h];div(rs,r,f,rs,r);}

  inline void addArray(bigInt &c, bigInt &a, bigInt &b){if((&c)==(&a))c.sz=add(a.sz,a.d,b.sz,b.d);else if((&c)==(&b))c.sz=add(b.sz,b.d,a.sz,a.d);else c.sz=add(a.sz,a.d,b.sz,b.d,c.d,workMemory);}
  inline void subArray(bigInt &c, bigInt &a, bigInt &b){if((&c)==(&a))c.sz=sub(a.sz,a.d,b.sz,b.d);else c.sz=add(a.sz,a.d,b.sz,b.d,c.d,workMemory);}
  inline int ArrayCmp(bigInt &a, bigInt &b){return cmp(a.sz,a.d,b.sz,b.d);}

  bigInt& operator+=(bigInt &a){if(a.sign==0)return*this;if(sign==0){set(a);return*this;}extend(max(sz,a.sz)+1);if(sign==a.sign)addArray(*this,*this,a);else{int k=ArrayCmp(*this,a);if(k==1)subArray(*this,*this,a);else if(k==-1)subArray(*this,a,*this),sign*=-1;else a.sign=a.sz=0;}return*this;}
  bigInt& operator-=(bigInt &a){if(a.sign==0)return*this;if(sign==0){set(a);sign*=-1;return*this;}extend(max(sz,a.sz)+1);if(sign!=a.sign)addArray(*this,*this,a);else{int k=ArrayCmp(*this,a);if(k==1)subArray(*this,*this,a);else if(k==-1)subArray(*this,a,*this),sign*=-1;else a.sign=a.sz=0;}return*this;}
  bigInt& operator*=(bigInt &a){if(sign==0)return*this;if(a.sign==0){set();return*this;}extend(sz+a.sz);sign*=a.sign;if(this==&a){int i;unsigned*t=(unsigned*)workMemory;rep(i,sz)t[i]=d[i];sz=mulKaratsuba(sz,d,sz,t,d,t+sz);}else sz=mulKaratsuba(sz,d,a.sz,a.d,d,workMemory);return*this;}
  bigInt& operator/=(bigInt &a){if(sign==0)return*this;sign*=a.sign;int dum;unsigned*memory=(unsigned*)workMemory;divKaratsuba(sz,d,a.sz,a.d,sz,d,dum,memory,memory+a.sz);if(sz==0)sign=0;return*this;}
  bigInt& operator%=(bigInt &a){if(sign==0)return*this;sign*=a.sign;int dum;unsigned*memory=(unsigned*)workMemory;divKaratsuba(sz,d,a.sz,a.d,dum,memory,sz,d,memory+max(0,sz-a.sz+1));if(sz==0)sign=0;return*this;}

  void addArray(unsigned val){int i;rep(i,sz){if(d[i]+val<d[i])d[i]+=val,val=1;else{d[i]+=val;val=0;break;}}if(val)extend(sz+1),d[sz++]=val;}
  void subArray(unsigned val){int i;if(sz==1){if(d[0]<val)sign=-sign,d[0]=val-d[0];else if(d[0]>val)d[0]-=val;else sz=sign=0;return;}rep(i,sz){if(d[i]<val)d[i]-=val,val=1;else{d[i]-=val;break;}}if(sz&&d[sz-1]==0)sz--;}
  void mulArray(unsigned val){int i;ull tmp=0;if(val==0){sign=sz=0;return;}if(val==1)return;extend(sz+1);rep(i,sz)tmp+=(ull)val*d[i],d[i]=tmp&0xFFFFFFFF,tmp>>=32;if(tmp)d[sz++]=tmp;}
  unsigned divArray(unsigned val){int i;ull tmp=0;if(val==1)return 0;for(i=sz-1;i>=0;i--)tmp=(tmp<<32)+d[i],d[i]=tmp/val,tmp%=val;if(sz&&d[sz-1]==0)sz--;if(sz==0)sign=0;return tmp;}

  bigInt& operator+=(int a){int f;unsigned v;if(a==0)return*this;if(sign==0){set(a);return*this;}if(a<0)f=-1,v=-((ll)a);else f=1,v=a;if(f==sign)addArray(v);else subArray(v);return*this;}
  bigInt& operator+=(unsigned a){if(a==0)return*this;if(sign==0){set(a);return*this;}if(sign==1)addArray(a);else subArray(a);return*this;}
  bigInt& operator-=(int a){int f;unsigned v;if(a==0)return*this;if(sign==0){set(a);sign*=-1;return*this;}if(a<0)f=-1,v=-((ll)a);else f=1,v=a;if(f!=sign)addArray(v);else subArray(v);return*this;}
  bigInt& operator-=(unsigned a){if(a==0)return*this;if(sign==0){set(a);sign*=-1;return*this;}if(sign!=1)addArray(a);else subArray(a);return*this;}
  bigInt& operator*=(int a){unsigned v;if(a==0){sz=sign=0;return*this;}if(sign==0)return*this;if(a<0)v=-((ll)a),sign*=-1;else v=a;mulArray(v);return*this;}
  bigInt& operator*=(unsigned a){if(a==0){sz=sign=0;return*this;}if(sign==0)return*this;mulArray(a);return*this;}
  bigInt& operator/=(int a){unsigned v;if(sign==0)return*this;if(a<0)v=-((ll)a),sign*=-1;else v=a;divArray(v);return*this;}
  bigInt& operator/=(unsigned a){if(sign==0)return*this;divArray(a);return*this;}

  void add(bigInt &a, bigInt &b){set(a);(*this)+=b;}
  void sub(bigInt &a, bigInt &b){set(a);(*this)-=b;}
  void mul(bigInt &a, bigInt &b){set(a);(*this)*=b;}
  void div(bigInt &a, bigInt &b){set(a);(*this)/=b;}
  void mod(bigInt &a, bigInt &b){set(a);(*this)%=b;}

  void divmod(bigInt &a, bigInt &b, bigInt *d, bigInt *r){d->extend(a.sz-b.sz+1);r->extend(b.sz);d->sign=r->sign=a.sign*b.sign;divKaratsuba(a.sz,a.d,b.sz,b.d,d->sz,d->d,r->sz,r->d,a.workMemory);if(d->sz==0)d->sign=0;if(r->sz==0)r->sign=0;}

  void reader(int as, unsigned arr[], int &rs, unsigned r[], void *work){int i,z;unsigned*s;if(as<300){rs=1;r[0]=arr[as-1];for(i=as-2;i>=0;i--)rs=mul(rs,r,1000000000U,r),rs=add(rs,r,arr[i]);return;}for(i=0;;i++){if(writerbase[i].sz==0)writerbase[i].extend(writerbase[i-1].sz*2),writerbase[i].sz=mulKaratsuba(writerbase[i-1].sz,writerbase[i-1].d,writerbase[i-1].sz,writerbase[i-1].d,writerbase[i].d,work),writerbase[i].sign=1;if((1<<i)>=as) break;}reader(as-(1<<(i-1)),arr+(1<<(i-1)),rs,r,work);rs=mulKaratsuba(rs,r,writerbase[i].sz,writerbase[i].d,r,work);s=(unsigned*)work;reader(1<<(i-1),arr,z,s,s+(1<<(i-1)));rs=add(rs,r,z,s);}
  void writer(int as, unsigned a[], int d, void *work){int i,x,y,z;unsigned*e,*b,*t;if(as<100){e=(unsigned*)work;b=e+9;t=b+as;x=as;rep(i,x)b[i]=a[i];y=0;while(x)t[y++]=div(x,b,1000000000U,x,b);if(d==-1){z=0;while(t[y-1])e[z++]=t[y-1]%10,t[y-1]/=10;for(i=z-1;i>=0;i--)mypc(e[i]+'0');y--;}else{i=(d-y)*9;while(i>0)i--,mypc('0');}while(y--){rep(i,9)e[i]=t[y]%10,t[y]/=10;rep(i,9)mypc(e[8-i]+'0');}}else{for(i=0;;i++){if(writerbase[i].sz==0)writerbase[i].mul(writerbase[i-1],writerbase[i-1]);if(writerbase[i].sz*2>=as)break;}b=(unsigned*)work;t=b+as-writerbase[i].sz+1;work=t+writerbase[i].sz;divKaratsuba(as,a,writerbase[i].sz,writerbase[i].d,x,b,y,t,work);writer(x,b,d==-1?-1:d-(1<<(i-1)),work);writer(y,t,1<<(i-1),work);}}

  bigInt(void){init();}
  void free(void){std::free(d);}
};

void *bigInt::workMemory;
bigInt *bigInt::writerbase;
void bigIntInit(int memsize=20){int i;bigInt::workMemory = malloc(memsize*1000000);bigInt::writerbase = (bigInt*) malloc(sizeof(bigInt)*40);bigInt::writerbase[0].init(1U);bigInt::writerbase[1].init(1000000000U);REP(i,2,40)bigInt::writerbase[i].init();}
void reader(bigInt *a){int i,j,k,sz=0,m=0;char*buf;unsigned*arr;for(;;){mygc(k);if(k=='-'){m=1;continue;}if('0'<=k&&k<='9'){break;}}buf=(char*)a->workMemory;buf[sz++]=k-'0';for(;;){mygc(k);if(k<'0'||k>'9')break;buf[sz++]=k-'0';}reverse(buf,buf+sz);arr=(unsigned*)(buf+sz);k=sz/9;rep(i,k){arr[i]=0;for(j=8;j>=0;j--)arr[i]=arr[i]*10+buf[i*9+j];}if(sz%9){arr[k]=0;for(j=sz%9-1;j>=0;j--)arr[k]=arr[k]*10+buf[k*9+j];k++;}if(k<100){a->set(arr[k-1]);for(i=k-2;i>=0;i--)(*a)*=1000000000U,(*a)+=arr[i];}else a->set(0),a->extend(k),a->sign=1,a->reader(k,arr,a->sz,a->d,arr+k);if(m)a->sign*=-1;}
void writer(bigInt &a, char h){if(a.sign!=0){if(a.sign==-1)mypc('-');a.writer(a.sz,a.d,-1,a.workMemory);}else mypc('0');mypc(h);}

#define SSE4_M32U_popcount(c,a) asm volatile("popcnt %1, %0;" : "=r"(c) : "r"(a))

int main(){
  int i, j, res = 0;
  bigInt k;

  bigIntInit(200);
  mint_init();

  reader(&k);
  rep(i,k.sz){
    SSE4_M32U_popcount(j,k.d[i]);
    res += j;
  }
  writerLn(res);

  return 0;
}