#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef __int128_t i128; typedef long double db; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=5e5+10; typedef vector<int> poly; const int P1=998244353,P2=1004535809; namespace DFT{ template<int p>inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%p; a=a*1ll*a%p;b>>=1; }return res; } template<int p>inline int add(int a,int b){if((a+=b)>=p)a-=p;return a;} int rev[1<<20],a[1<<20],b[1<<20],mul[1<<20]; void init(int n){up(i,0,(1<<n)-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<n-1);} template<int p>void dft(int n,int *a,int op){ const int G=3,Gi=(p+1)/3; init(n);up(i,0,(1<<n)-1)if(i<rev[i])swap(a[i],a[rev[i]]); for(int k=1;k<(1<<n);k<<=1){ int v=qp<p>((op==1)?G:Gi,(p-1)/k/2); mul[0]=1;up(i,1,k-1)mul[i]=mul[i-1]*1ll*v%p; for(int i=0;i<(1<<n);i+=k<<1) up(j,i,i+k-1){ int x=a[j],y=a[j+k]*1ll*mul[j-i]%p; a[j]=add<p>(x,y),a[j+k]=add<p>(x,p-y); } } if(op==-1){ int iv=qp<p>((p+1)/2,n); up(i,0,(1<<n)-1)a[i]=a[i]*1ll*iv%p; } } template<int p>poly conv(poly A,poly B){ if(A.empty()||B.empty())return {}; if(A.size()<=15||B.size()<=15){ poly C(A.size()+B.size()-1,0); up(i,0,A.size()-1) up(j,0,B.size()-1) C[i+j]=(C[i+j]+A[i]*1llu*B[j])%p; return C; } int n=0; while((1<<n)<A.size()+B.size()-1)n++; up(i,0,(1<<n)-1)a[i]=b[i]=0; up(i,0,A.size()-1)a[i]=A[i]; up(i,0,B.size()-1)b[i]=B[i]; dft<p>(n,a,1),dft<p>(n,b,1); up(i,0,(1<<n)-1)a[i]=a[i]*1ll*b[i]%p; dft<p>(n,a,-1);poly C; up(i,0,A.size()+B.size()-2)C.eb(a[i]); return C; } } const int z=DFT::qp<P2>(P1,P2-2); const int M=(1<<18)-1; inline int add(int a,int b){return (a+b)&M;} namespace CRT{ int mer(int r1,int r2){ ll k=r2-r1;if(k<0)k+=P2;k=k*z%P2; ll C=r1+k*P1; return C&M; } } poly operator+(poly a,poly b){ if(a.size()<b.size())a.swap(b); up(i,0,(int)b.size()-1)a[i]=add(a[i],b[i]); return a; } poly operator-(poly a,poly b){ for(int &x:b)x=x?(M+1-x):0; return a+b; } poly operator*(poly a,poly b){ auto v1=DFT::conv<P1>(a,b); auto v2=DFT::conv<P2>(a,b); vector<int>res(v1.size()); up(i,0,(int)v1.size()-1)res[i]=CRT::mer(v1[i],v2[i]); return res; } poly inv(poly a){ poly g={M}; for(int s=1;s<a.size();s<<=1){ poly f=a;f.resize(s<<1); f=f*g;f.resize(s<<1); f=f*g;f.resize(s<<1); g=g+g;g=g-f; } g.resize(a.size());return g; } void slv(){ string s;cin>>s; int n=s.size();vector<int>S(n+1,0); up(i,1,n)S[i]=s[i-1]-'0'; vector<int>f={1}; for(int s=1;s<n+1;s<<=1){ poly g=S;g.resize(s<<1); auto it=f*f; up(i,0,(int)f.size()-1)it[i*2]=add(it[i*2],f[i]); for(int&x:it)x/=2;it=it*g;it.resize(s<<1); it=it-f;it[0]=add(it[0],1); auto it2=f*g;it2[0]=add(it2[0],M);it2=inv(it2); it=it*it2;it.resize(s<<1); f=f-it; } up(i,1,n)printf("%d",f[i]&1); } int main(){ // freopen("1.in","r",stdin),freopen("1.out","w",stdout); slv(); return 0; }