BigInteger 高精度

const int _bod_=10000;
struct BN{
    static const int N=1010;int a[N];
    BN(){memset(a,0,sizeof(a));}
    int& operator [](int n){return a[n];}
    BN operator =(int n){
         memset(a,0,sizeof(a));
         a[1]=n;if(a[1])a[0]=1;
         while(a[a[0]+1]){a[a[0]+1]=a[a[0]]/_bod_;a[a[0]++]%=_bod_;}
         return *this;
    }
    bool operator <(BN b) const{
        if(a[0]<b[0])return 1;
        if(a[0]>b[0])return 0;
        for(int i=a[0];i>=1;i--){
            if(a[i]>b[i])return 0;
            if(a[i]<b[i])return 1;
        }
        return 0;
    }
    BN operator +(BN b) const{
        b[0]=max(a[0],b[0]);
        for(int i=1;i<=b[0];i++){
            b[i]+=a[i];
            if(b[i]>=_bod_){b[i+1]+=b[i]/_bod_;b[i]%=_bod_;}
        }
        if(b[b[0]+1])b[0]++;
        return b;
    }
    BN operator -(BN b) const{
        BN ans=*this;int q=1;
        if(ans<b)swap(ans,b),q=-1;
        for(int i=1;i<=ans[0];i++){
            ans[i]=ans[i]-b[i];
            if(ans[i]<0){ans[i+1]--;ans[i]+=_bod_;}
        }
        while(ans[0]&&!ans[ans[0]])ans[0]--;
        for(int i=1;i<=ans[0];i++)ans[i]*=q;
        return ans;
    }
    BN operator *(BN b) const{
        BN ans;
        ans[0]=a[0]+b[0]-1;
        for(int i=1;i<=a[0];i++)
            for(int o=1;o<=b[0];o++){
                int now=i+o-1;
                ans[now]+=a[i]*b[o];
            }
        for(int i=1;i<=ans[0];i++)if(ans[i]>=_bod_){ans[i+1]+=ans[i]/_bod_;ans[i]%=_bod_;}
        if(ans[ans[0]+1])ans[0]++;
        return ans;
    }
    void operator +=(BN b){*this=*this+b;}
    void operator -=(BN b){*this=*this-b;}
    void operator *=(BN b){*this=*this*b;}
    void print(){printf("%d",a[a[0]]);for(int i=a[0]-1;i>=1;i--)printf("%.4d",a[i]);}//.xd x=_bod_后导零的个数(位数)
};