const i64 MOD=10000000; class BigNum { public: i64 a[1200]; public: BigNum operator+(BigNum temp) { BigNum ans; i64 i,j,k,p; if(a[0]>temp.a[0]) p=a[0]; else p=temp.a[0]; for(i=a[0],j=temp.a[0],k=p;j>=1&&i>=1;i--,j--,k--) ans.a[k]=a[i]+temp.a[j]; if(j==0) { while(i>=1) ans.a[i]=a[i--]; } else { while(j>=1) ans.a[j]=temp.a[j--]; } ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p+1;i>=1;i--) ans.a[i]=ans.a[i-1]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator-(BigNum temp) { BigNum ans; int i,j; for(i=0;i<=a[0];i++) ans.a[i]=a[i]; for(i=ans.a[0],j=temp.a[0];i>=1&&j>=1;i--,j--) ans.a[i]-=temp.a[j]; for(i=ans.a[0];i>=1;i--) if(ans.a[i]<0) { ans.a[i]+=MOD; ans.a[i-1]--; } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator*(BigNum temp) { BigNum ans; int i,j,p=a[0]+temp.a[0]-1; memset(ans.a,0,sizeof(ans.a)); for(i=a[0];i>=1;i--) for(j=temp.a[0];j>=1;j--) ans.a[i+j-1]+=a[i]*temp.a[j]; ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p;i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator*(int temp) { BigNum ans; int i; for(i=1;i<=a[0];i++) ans.a[i]=a[i]*temp; ans.a[0]=0; for(i=a[0];i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=a[0]+1; } else ans.a[0]=a[0]; if(ans.a[1]>=MOD) { for(i=ans.a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]++; } return ans; } BigNum operator/(int x) { BigNum ans; int i,j; i64 p; for(i=1;i<=a[0];i++) { if(i==1) { ans.a[i]=a[i]/x; p=a[i]%x; } else { ans.a[i]=(p*MOD+a[i])/x; p=(p*MOD+a[i])%x; } } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator/(BigNum temp) { BigNum ans,t; BigNum low=BigNum(1),high,mid; int i; for(i=1;i<=a[0];i++) t.a[i]=high.a[i]=a[i]; t.a[0]=high.a[0]=a[0]; while(!(low>high)) { mid=(low+high)/2; if(mid*temp>t) high=mid-BigNum(1); else low=mid+BigNum(1); } if(!(low>t)&&!(temp*low>t)) return low; return high; } BigNum operator%(BigNum temp) { int i; BigNum t; for(i=1;i<=a[0];i++) t.a[i]=a[i]; t.a[0]=a[0]; return t-t/temp*temp; } public: BigNum() { a[0]=1; a[1]=0; } BigNum(int x) { if(x>=MOD) a[0]=2,a[1]=x/MOD,a[2]=x%MOD; else a[0]=1,a[1]=x; } BigNum(i64 x) { stack<i64> s; while(x) { s.push(x%MOD); x/=MOD; } a[0]=s.size(); int k=0; while(!s.empty()) { a[++k]=s.top(); s.pop(); } } BigNum(string str) { int i; for(i=0;i<str.length();i++) if(str[i]!='0') break; if(i==str.length()) { a[0]=1; a[1]=0; return; } str=str.substr(i,str.length()-i); int p=str.length()%7,j; i64 k; a[0]=0; if(p) { a[0]=1; k=0; for(i=0;i<p;i++) k=k*10+str[i]-'0'; a[1]=k; str=str.substr(p,str.length()-p); } for(i=0;i<str.length();) { k=0; for(j=i;j<i+7;j++) k=k*10+str[j]-'0'; a[++a[0]]=k; i=j; } } int operator==(BigNum temp) { if(a[0]!=temp.a[0]) return 0; for(int i=1;i<=a[0];i++) if(a[i]!=temp.a[i]) return 0; return 1; } int operator>(BigNum temp) { if(a[0]>temp.a[0]) return 1; if(a[0]<temp.a[0]) return 0; for(int i=1;i<=a[0];i++) if(a[i]!=temp.a[i]) return a[i]>temp.a[i]; return 0; } void print() { printf("%I64d",a[1]); for(int i=2;i<=a[0];i++) printf("%07d",(int)a[i]); } };