#ifndef BIGNUM#define BIGNUMclass BigNum {#define MAXSIZEOFBIGNUM 500#define BASE 10#define DLEN 1public:    int Len;    int d[MAXSIZEOFBIGNUM];public:    BigNum(void);    BigNum(const int);    BigNum(const char *);    BigNum(const BigNum &);    BigNum & operator = (const BigNum &);    void clear(void);    friend istream& operator>>(istream&, BigNum&);    friend ostream& operator<<(ostream&, BigNum&);    bool operator == (const BigNum &) const;    bool operator > (const BigNum &) const;    bool operator < (const BigNum &) const;    bool operator >= (const BigNum &) const;    bool operator <= (const BigNum &) const;    BigNum operator + (const BigNum &) const;    BigNum operator - (const BigNum &) const;    BigNum operator * (const BigNum &) const;    BigNum operator / (const BigNum &) const;    BigNum operator % (const BigNum &) const;    void operator ++ (void);    void operator -- (void);    BigNum operator + (const int &) const;    BigNum operator - (const int &) const;    BigNum operator * (const int &) const;    BigNum operator / (const int &) const;    int operator % (const int &) const;    BigNum operator ^ (const int &) const;    ~BigNum() {}};BigNum::BigNum() {    Len = 0;    memset(d, 0, sizeof(d));}BigNum::BigNum(const int ops) {    int x = ops;    Len = 0;    memset(d, 0, sizeof(d));    while(x) {        Len++;        d[Len] = x % BASE;        x /= BASE;    }}BigNum::BigNum(const char * ops) {    int L = strlen(ops) - 1, b = 0;    memset(d, 0, sizeof(d));    while(ops[b] == ‘0‘) {        b++;    }    Len = 0;    while(L - b + 1 >= DLEN) {        int x = 0;        for(int i = L - DLEN + 1; i <= L; i++) {            x = x * 10 + ops[i] - ‘0‘;        }        Len++;        d[Len] = x;        L -= DLEN;    }    int x = 0;    for(int i = b; i <= L; i++) {        x = x * 10 + ops[i] - ‘0‘;    }    Len++;    d[Len] = x;}BigNum::BigNum(const BigNum &ops) : Len(ops.Len) {    memset(d, 0, sizeof(d));    for(int i = 1; i <= Len; i++) {        d[i] = ops.d[i];    }}BigNum & BigNum::operator = (const BigNum &ops) {    memset(d, 0, sizeof(d));    Len = ops.Len;    for(int i = 1; i <= Len; i++) {        d[i] = ops.d[i];    }    return *this;}void BigNum::clear(void) {    for(int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) {        if(d[i] < 0) {            d[i] += BASE;            d[i + 1]--;        }        if(d[i] >= BASE) {            d[i] -= BASE;            d[i + 1]++;        }    }    for(int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)        if(d[i] > 0) {            Len = i;            return;        }    Len = 0;}istream& operator>>(istream &in, BigNum &ops) {    char str[MAXSIZEOFBIGNUM + 100];    in >> str;    int L = strlen(str), b = 0;    while(str[b] == ‘0‘) {        b++;    }    ops.Len = 0;    for(int i = L - 1; i >= b; i--) {        ops.Len++;        ops.d[ops.Len] = str[i] - ‘0‘;    }    return in;}ostream& operator<<(ostream& out, BigNum& ops) {    for(int i = ops.Len; i >= 1; i--) {        out << ops.d[i];    }    if(ops.Len == 0) {        out << "0";    }    return out;}bool BigNum::operator == (const BigNum &ops) const {    if(Len != ops.Len) {        return false;    }    for(int i = Len; i >= 1; i--)        if(d[i] != ops.d[i]) {            return false;        }    return true;}bool BigNum::operator > (const BigNum &ops) const {    if(Len < ops.Len) {        return false;    } else if(Len > ops.Len) {        return true;    } else {        for(int i = Len; i >= 1; i--)            if(d[i] < ops.d[i]) {                return false;            } else if(d[i] > ops.d[i]) {                return true;            }    }    return false;}bool BigNum::operator < (const BigNum &ops) const {    if(Len < ops.Len) {        return true;    } else if(Len > ops.Len) {        return false;    } else {        for(int i = Len; i >= 1; i--)            if(d[i] < ops.d[i]) {                return true;            } else if(d[i] > ops.d[i]) {                return false;            }    }    return false;}bool BigNum::operator >= (const BigNum &ops) const {    if(Len < ops.Len) {        return false;    } else if(Len > ops.Len) {        return true;    } else {        for(int i = Len; i >= 1; i--)            if(d[i] < ops.d[i]) {                return false;            } else if(d[i] > ops.d[i]) {                return true;            }    }    return true;}bool BigNum::operator <= (const BigNum &ops) const {    if(Len < ops.Len) {        return true;    } else if(Len > ops.Len) {        return false;    } else {        for(int i = Len; i >= 1; i--)            if(d[i] < ops.d[i]) {                return true;            } else if(d[i] > ops.d[i]) {                return false;            }    }    return true;}BigNum BigNum::operator + (const BigNum &ops) const {    BigNum ret(*this);    for(int i = 1; i <= ops.Len; i++) {        ret.d[i] += ops.d[i];    }    ret.clear();    return ret;}BigNum BigNum::operator - (const BigNum &ops) const {    BigNum ret(*this);    for(int i = ops.Len; i >= 1; i--) {        ret.d[i] -= ops.d[i];    }    ret.clear();    return ret;}BigNum BigNum::operator * (const BigNum &ops) const {    BigNum ret, now(*this);    for(int i = 1; i <= now.Len; i++)        for(int j = 1; j <= ops.Len; j++) {            ret.d[i + j - 1] += now.d[i] * ops.d[j];        }    for(int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)        if(ret.d[i] >= BASE) {            ret.d[i + 1] += ret.d[i] / BASE;            ret.d[i] %= BASE;        }    for(int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)        if(ret.d[i] > 0) {            ret.Len = i;            break;        }    return ret;}BigNum BigNum::operator / (const BigNum &ops) const {    BigNum now = (*this), div, mod;    div.Len = now.Len;    mod.Len = 0;    for(int j = now.Len; j >= 1; j--) {        mod.Len++;        for(int p = mod.Len; p >= 2; p--) {            mod.d[p] = mod.d[p - 1];        }        mod.d[1] = now.d[j];        while(mod >= ops) {            div.d[j]++;            mod = mod - ops;        }        if(mod.Len == 1 && mod.d[1] == 0) {            mod.Len--;        }    }    div.clear();    mod.clear();    return div;}BigNum BigNum::operator % (const BigNum &ops) const {    BigNum now = (*this), div, mod;    div.Len = now.Len;    mod.Len = 0;    for(int j = now.Len; j >= 1; j--) {        mod.Len++;        for(int p = mod.Len; p >= 2; p--) {            mod.d[p] = mod.d[p - 1];        }        mod.d[1] = now.d[j];        while(mod >= ops) {            div.d[j]++;            mod = mod - ops;        }        if(mod.Len == 1 && mod.d[1] == 0) {            mod.Len--;        }    }    div.clear();    mod.clear();    return mod;}void BigNum::operator ++ (void) {    d[1]++;    for(int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)        if(d[i] >= BASE) {            d[i] -= BASE;            d[i + 1]++;        } else {            break;        }    if(d[Len + 1] > 0) {        Len++;    }}void BigNum::operator -- (void) {    d[1]--;    for(int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)        if(d[i] < 0) {            d[i] += BASE;            d[i + 1]--;        } else {            break;        }    if(d[Len] == 0) {        Len--;    }}BigNum BigNum::operator + (const int & ops) const {    BigNum ret = (*this);    ret.d[1] += ops;    ret.clear();    return ret;}BigNum BigNum::operator - (const int & ops) const {    BigNum ret = (*this);    ret.d[1] -= ops;    ret.clear();    return ret;}BigNum BigNum::operator * (const int & ops) const {    BigNum ret(*this);    for(int i = 1; i <= ret.Len; i++) {        ret.d[i] *= ops;    }    for(int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)        if(ret.d[i] >= BASE) {            ret.d[i + 1] += ret.d[i] / BASE;            ret.d[i] %= BASE;        }    for(int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)        if(ret.d[i] > 0) {            ret.Len = i;            return ret;        }    ret.Len = 0;    return ret;}BigNum BigNum::operator / (const int & ops) const {    BigNum ret;    int down = 0;    for(int i = Len; i >= 1; i--) {        ret.d[i] = (d[i] + down * BASE) / ops;        down = d[i] + down * BASE - ret.d[i] * ops;    }    ret.Len = Len;    while(ret.d[ret.Len] == 0 && ret.Len > 1) {        ret.Len--;    }    return ret;}int BigNum::operator % (const int &ops) const {    int mod = 0;    for(int i = Len; i >= 1; i--) {        mod = ((mod * BASE) % ops + d[i]) % ops;    }    return mod;}BigNum BigNum::operator ^ (const int &ops) const {    BigNum t, ret(1);    if(ops == 0) {        return ret;    }    if(ops == 1) {        return *this;    }    int m = ops, i;    while(m > 1) {        t = *this;        for(i = 1; (i << 1) <= m; i <<= 1) {            t = t * t;        }        m -= i;        ret = ret * t;        if(m == 1) {            ret = ret * (*this);        }    }    return ret;}#endif