#include <vector>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>

using namespace std;


typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;

#ifdef _MSC_VER
    const ld M_PI=(ld)3.1415926535897932384626433832795;
#endif


namespace Numbers
{
    class Lint
    {
    private:
        static const int base=1e6;
        static const int LOG_BASE=6;
        static const int BIG_NUM_SZ=1e6;
        static const Lint ONE;

        vector <int> v;
        bool sgn;
    public:
        Lint();
        Lint(int a);
        Lint(unsigned int a);
        Lint(ll a);
        Lint(ull a);
        Lint(const char* s);
        Lint(const string& s);

        /*operator bool();*/
        Lint operator -();
        Lint& operator +=(Lint b);
        Lint& operator -=(Lint b);
        Lint& operator *=(const Lint& b);
        Lint& operator /=(const Lint& b);
        Lint& operator %=(const Lint& b);
        Lint& operator +=(ll b);
        Lint& operator -=(ll b);
        Lint& operator *=(ll b);
        Lint& operator /=(ll b);
        Lint& operator %=(ll b);
        Lint& operator ++();
        Lint operator ++(int);
        Lint& operator --();
        Lint operator --(int);

        friend Lint operator +(const Lint&,const Lint&);
        friend Lint operator -(const Lint&,const Lint&);
        friend Lint operator *(const Lint&,const Lint&);
        friend Lint operator /(const Lint&,const Lint&);
        friend Lint operator %(const Lint&,const Lint&);
        friend Lint operator /(const Lint&,ll);
        friend Lint operator %(const Lint&,ll);
        friend bool operator <(const Lint&,const Lint&);
        friend bool operator ==(const Lint&,const Lint&);
        friend bool operator >(const Lint&,const Lint&);
        friend bool operator !=(const Lint&,const Lint&);
        friend bool operator <=(const Lint&,const Lint&);
        friend bool operator >=(const Lint&,const Lint&);
        friend istream& operator >>(istream&,Lint&);
        friend ostream& operator <<(ostream&,const Lint&);

        string std_str() const;
        const char* c_str() const;

    private:
        class Complex {/*definition here...*/};
        friend void fft(vector <Complex>&,bool);

        void fast_mul(const Lint& b) {/*can't use fft from here*/};
    };

    const Lint Lint::ONE=1;

    void fft(vector <Lint::Complex>& a,bool inv) {/*fft cod here...*/}
};

typedef Numbers::Lint Lint;