#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <complex>
#include <cmath>
#include <cassert>
#include <cstring>

using namespace std;

typedef unsigned short dig;
typedef unsigned int u64;

#define DIGM ( ~(dig)(0) )
#define DIGL ( 8 * sizeof(dig) )

#define sz size()

typedef complex<long double> base;

typedef vector<dig> bi;

int rev[1000000];
base wlen_pw[1000000];
base fa[1000000];
base fb[1000000];

#define BASE10 100
#define BASE10L 2

bi digits[BASE10+1];

#define MAXN (10000000+100500)

char s[MAXN];

void print(bi x, char * s) {
    int j = DIGL - 1;
    if(!x.sz) {
        *s++ = '0';
        *s++ = 0;
        return ;
    }
    while( !((x[x.sz-1]>>j)&1) )
        --j;
    while(j >= 0)
        *s++ = '0' + ((x[x.sz-1]>>(j--))&1);
    int i = x.sz-2;
    while(i>=0) {
        j = DIGL - 1;
        do
            *s++ = '0' + ((x[i]>>(j--))&1);
        while(j >= 0);
        --i;
    }
    *s++ = 0;
}

void fft (base a[], int n, bool invert) {
	for (int i=0; i<n; ++i)
		if (i < rev[i])
			swap (a[i], a[rev[i]]);

	for (int len=2; len<=n; len<<=1) {
		long double ang = 2*M_PI/len * (invert?-1:+1);
		int len2 = len>>1;

		base wlen (cosl(ang), sinl(ang));
		wlen_pw[0] = base (1, 0);
		for (int i=1; i<len2; ++i)
			wlen_pw[i] = wlen_pw[i-1] * wlen;

		for (int i=0; i<n; i+=len) {
			base t,
				*pu = a+i,
				*pv = a+i+len2,
				*pu_end = a+i+len2,
				*pw = wlen_pw;
			for (; pu!=pu_end; ++pu, ++pv, ++pw) {
				t = *pv * *pw;
				*pv = *pu - t;
				*pu += t;
			}
		}
	}

	if (invert)
		for (int i=0; i<n; ++i)
			a[i] /= n;
}

void calc_rev (int n, int log_n) {
	for (int i=0; i<n; ++i) {
		rev[i] = 0;
		for (int j=0; j<log_n; ++j)
			if (i & (1<<j))
				rev[i] |= 1<<(log_n-1-j);
	}
}

typedef vector<dig> bi;

bi mul(bi op1, bi op2) {
	size_t n = 1;
	size_t logn = 0;
	while (n < max (op1.size(), op2.size())) n <<= 1, logn += 1;
	n <<= 1; logn += 1;
	for(int i = 0; i < op1.sz; ++i) fa[i] = op1[i];
	for(int i = op1.sz; i < n; ++i) fa[i] = 0;
	for(int i = 0; i < op2.sz; ++i) fb[i] = op2[i];
	for(int i = op2.sz; i < n; ++i) fb[i] = 0;
    calc_rev(n, logn);
    //for(int i = 0; i < n; ++i) cerr << fa[i] << ' '; cerr << '\n';
    //for(int i = 0; i < n; ++i) cerr << fb[i] << ' '; cerr << '\n';
	fft (fa, n, false),  fft (fb, n, false);
	for (size_t i = 0; i < n; ++i)
		fa[i] *= fb[i];
	fft (fa, n, true);
	//for(int i = 0; i < n; ++i) cerr << fa[i] << ' '; cerr << '\n';
	bi res(n);
	unsigned long long t = 0, carry = 0;
	for (size_t i=0; i<n; ++i) {
	    t = (unsigned long long)(fa[i].real() + 0.5) + carry;
	    res[i] = (dig)(t & DIGM);
	    carry = t >> DIGL;
	}
	while(!res.empty() && !res.back())
        res.pop_back();
    return res;
}

/*bi mul(bi op1, bi op2) {
    bi res(op1.sz + op2.sz);
    for(int i = 0; i < op1.sz; ++i) {
        dig carry = 0;
        u64 t;
        int j;
        for(j = 0; j < op2.sz; ++j) {
            t = op1[i];
            t *= op2[j];
            t += res[i+j];
            t += carry;
            res[i+j] = t & DIGM;
            carry = t >> DIGL;
        }
        while(carry) {
            t = res[i+j] + carry;
            res[i+j] = t & DIGM;
            carry = t >> DIGL;
            ++j;
        }
    }
    while(res.sz > 0 && res[res.sz-1] == 0)
        res.pop_back();
    return res;
}*/

int max(int i, int j) { return i < j ? j : i; }

bi sum(bi op1, bi op2) {
    bi res(max(op1.sz, op2.sz)+1);
    dig carry = 0;
    u64 t;
    int i;
    for(i = 0; i < op1.sz && i < op2.sz; ++i) {
        t = op1[i];
        t += op2[i];
        t += carry;
        res[i] = t & DIGM;
        carry = t >> DIGL;
    }
    for(; i < op1.sz; ++i) {
        t = op1[i];
        t += carry;
        res[i] = t & DIGM;
        carry = t >> DIGL;
    }
    for(; i < op2.sz; ++i) {
        t = op2[i];
        t += carry;
        res[i] = t & DIGM;
        carry = t >> DIGL;
    }
    if(carry)
        res[i] = carry;
    while(res.sz > 0 && res[res.sz-1] == 0)
        res.pop_back();
    return res;
}

bi read(char * s) {
    int n = strlen(s);
    bi res((n + BASE10L)/BASE10L);
    int l = 0;
    for(int i = n; i > 0; i -= BASE10L) {
        char si = s[i];
        s[i] = 0;
        res[l++] = atoi(s+max(i-BASE10L, 0));
        s[i] = si;
    }
    return res;
}

bi step[20];

bi go(bi x) {
    if(!x.sz) return bi(0);
    if(x.sz <= 1) return bi(1, x[0]);
    int i = 1;
    while( (1<<(i-1)) < x.sz) ++i; --i;
    int l = (1 << (i-1));
    bi y = bi(x.begin() + l, x.end());
    x.resize(l);
    return sum(mul(go(y), step[i]) , go(x));
}

bi solve2(bi x) {
    step[0] = bi(1, 1);
    step[1] = bi(1, BASE10);
    for(int i = 2; (1<<(i-1)) < x.sz; ++i)
        step[i] = mul(step[i-1], step[i-1]);
    return go(x);
}


int main() {
    for(int i = 0; i <= BASE10; ++i) {
        digits[i] = bi(1, i);
    }
    gets(s);
    if( strlen(s) == 1 && s[0] == '0' ) { puts("0"); return 0; }
    bi input = read(s);
    bi ans = solve2(input);
    print(ans, s);
    puts(s);
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:231:5: error: ‘gets’ was not declared in this scope; did you mean ‘getw’?
  231 |     gets(s);
      |     ^~~~
      |     getw