struct BigNum{
    static const int BASE = 10000000;
    static const int base = 7;
    long long d[20];
    int len;
    BigNum(){
        len = 1;
        d[1] = 0;
    }
    BigNum(const string &s){
        len = 1;
        d[1] = 0;
        for(int i = s.length() - 1, t = 1; i >= 0; i--, t *= 10){
            if (t == BASE){
                t = 1;
                d[++len] = 0;
            }
            d[len] += (s[i] - '0') * t;
        }
    }
    BigNum(const char* s){
        len = 1;
        d[1] = 0;
        for(int i = strlen(s) - 1, t = 1; i >= 0; i--, t *= 10){
            if (t == BASE){
                t = 1;
                d[++len] = 0;
            }
            d[len] += (s[i] - '0') * t;
        }
    }
    BigNum& operator =(const BigNum &a){
        len = a.len;
        for(int i = 1; i <= len; i++)
            d[i] = a.d[i];
        return *this;
    }
    BigNum& operator =(const string &s){
        len = 1;
        d[1] = 0;
        for(int i = s.length() - 1, t = 1; i >= 0; i--, t *= 10){
            if (t == BASE){
                t = 1;
                d[++len] = 0;
            }
            d[len] += (s[i] - '0') * t;
        }
        return *this;
    }
    BigNum& operator =(const char* s){
        len = 1;
        d[1] = 0;
        for(int i = strlen(s) - 1, t = 1; i >= 0; i--, t *= 10){
            if (t == BASE){
                t = 1;
                d[++len] = 0;
            }
            d[len] += (s[i] - '0') * t;
        }
        return *this;
    }
    BigNum operator +(const BigNum &a)const{
        static BigNum c;
        c.len = a.len;
        if (len > c.len) c.len = len;
        c.d[c.len + 1] = 0;
        for(int i = 1; i <= c.len; i++) c.d[i] = d[i];
        for(int i = 1; i <= a.len; i++){
            c.d[i] += a.d[i];
        }
        for(int i = 1; i <= c.len; i++)
            if (c.d[i] >= BASE){
                c.d[i + 1]++;
                c.d[i] -= BASE;
            }
        if (c.d[c.len + 1]) c.len++;
        return c;
    }
    BigNum operator -(const BigNum &a)const{// *this >= a
        static BigNum c;
        c.len = len;
        for(int i = 1; i <= c.len; i++) c.d[i] = d[i];
        for(int i = 1; i <= a.len; i++){
            c.d[i] -= a.d[i];
        }
        for(int i = 1; i < c.len; i++){
            if (c.d[i] < 0){
                c.d[i] += BASE;
                c.d[i + 1]--;
            }
        }
        while (c.len > 1 && c.d[c.len] == 0) c.len--;
        return c;
    }
    BigNum operator *(const int a)const{
        static BigNum b;
        b.len = len;
        for(int i = 1; i <= len; i++) b.d[i] = d[i] * a;
        b.d[len + 1] = 0;
        for(int i = 1; i <= len; i++) if (b.d[i] >= BASE){
            b.d[i + 1] += b.d[i] / BASE;
            b.d[i] %= BASE;
        }
        if (b.d[b.len + 1]) b.len++;
        return b;
    }
    BigNum operator *(const BigNum &b)const{
        static BigNum c;
        static long long te; 
        c.len = len + b.len;
        for(int i = 1; i <= c.len; i++) c.d[i] = 0;
        for(int i = 1; i <= len; i++)
            for(int j = 1; j <= b.len; j++)
                c.d[i + j - 1] += d[i] * b.d[j];
        for(int i = 1; i < c.len; i++)
            if (c.d[i] >= BASE){
                te = c.d[i] / BASE;
                c.d[i + 1] += te;
                c.d[i] -= te * BASE;
            }
        while (c.len > 1 && c.d[c.len] == 0) c.len--;
        return c;
    }
    BigNum operator /(const int a)const{
        static BigNum b;
        b.len = len;
        for(int i = 1; i <= len; i++) b.d[i] = d[i];
        for(int i = b.len; i > 1; i--){
            b.d[i - 1] += b.d[i] % a * BASE;
            b.d[i] /= a;
        }
        b.d[1] /= a;
        while (b.len > 1 && b.d[b.len] == 0) b.len--;
        return b;
    }
    BigNum operator /(const BigNum &b)const{
        static BigNum c, w, t, n;
        static int k;
        c = "0";
        t = b;
        w = "1";
        k = 0;
        while (t <= *this){
            t = t + t;
            w = w + w;
            k++;
        }
        n = *this;
        while (k--){
            t = t / 2;
            w = w / 2; 
            if (n >= t){
                n = n - t;
                c = c + w;
            }
        }
        return c;
    }
    BigNum operator %(const BigNum &b)const{
        static BigNum t, n;
        static int k;
        t = b;
        k = 0;
        while (t <= *this){
            t = t + t;
            k++;
        }
        n = *this;
        while (k--){
            t = t / 2;
            if (n >= t){
                n = n - t;
            }
        }
        return n;
    }
    bool operator <(const BigNum &a)const{
        if (len < a.len) return 1;
        if (len > a.len) return 0;
        for(int i = len; i >= 1; i--){
            if (d[i] < a.d[i]) return 1;
            if (d[i] > a.d[i]) return 0;
        }
        return 0;
    }
    bool operator >(const BigNum &a)const{
        if (len < a.len) return 0;
        if (len > a.len) return 1;
        for(int i = len; i >= 1; i--){
            if (d[i] < a.d[i]) return 0;
            if (d[i] > a.d[i]) return 1;
        }
        return 0;
    }    
    bool operator <=(const BigNum &a)const{
        return !(*this > a);
    }
    bool operator >=(const BigNum &a)const{
        return !(*this < a);
    }
    bool operator ==(const BigNum &a)const{
        if (len != a.len) return 0;
        for(int i = len; i >= 1; i--){
            if (d[i] != a.d[i]) return 0;
        }        
        return 1;
    }
    bool operator !=(const BigNum &a)const{
        return !(*this == a);
    }    
    friend istream& operator >>(istream & instream, BigNum &a){    
        static string t;
        instream >> t;
        a = t;
        return instream;
    }    
    friend ostream& operator <<(ostream & outstream, const BigNum &a){    
        outstream << a.d[a.len];
        for(int i = a.len - 1; i >= 1; i--) outstream << setw(base) << setfill('0') << a.d[i];
        cout << endl;
        return outstream;
    }
    static BigNum BigNumPow(BigNum a, int k){
        static BigNum ans;
        ans = "1";
        while (k){
            if (k & 1) ans = ans * a;
            a = a * a;
            k >>= 1;
        }
        return ans;
    }
};