#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin()) #define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin()) using ll=long long int; using ull=unsigned long long; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} templateT ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);} templateT floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);} templateint popcnt(T x){return __builtin_popcountll(x);} templateint topbit(T x){return (x==0?-1:63-__builtin_clzll(x));} templateint lowbit(T x){return (x==0?-1:__builtin_ctzll(x));} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__int128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__uint128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(double x){ ostringstream oss; oss << fixed << setprecision(15) << double(x); string s = oss.str(); _write(s); } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ _write(head); write(tail...); if(space)_write(' '); } inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/Convolution/fft.hpp" namespace FFT{ struct C{ double x,y; C(double _x=0,double _y=0):x(_x),y(_y){} C operator~()const{return C(x,-y);} C operator*(const C& c)const{return C(x*c.x-y*c.y,x*c.y+y*c.x);} C operator+(const C& c)const{return C(x+c.x,y+c.y);} C operator-(const C& c)const{return C(x-c.x,y-c.y);} }; vector> w(1,vector(1,1)); void init(int lg){ for(int d=1,m=1;d<=lg;d++,m<<=1)if(d>=(int)w.size()){ w.emplace_back(m); const double th=M_PI/m; for(int i=0;i>1]); } } void fft(vector& f,bool inv){ const int n=f.size(); const int lg=__lg(n); if(lg>=(int)w.size())init(lg); if(inv){ for(int k=1;k<=lg;k++){ const int d=1<<(k-1); for(int s=0;svector mult(const vector& a,const vector& b){ const int as=a.size(); const int bs=b.size(); if(!as or !bs)return {}; const int cs=as+bs-1; vector c(cs); if(max(as,bs)<16){ for(int i=0;i f(n); for(int i=0;ij)continue; C x=f[i]+~f[j],y=f[i]-~f[j]; f[i]=x*y*rad; f[j]=~f[i]; } fft(f,1); for(int i=0;ivector square(const vector& a){ const int as=a.size(); if(!as)return {}; const int cs=as*2-1; vector c(cs); if(as<16){ for(int i=0;i f(n); for(int i=0;istruct bigint{ static const int B=pow(10,D); int sign=0; vector v; static int get_D(){return D;} static int get_B(){return B;} bigint(ll x=0){ if(x<0)x*=-1,sign=1; while(x){v.push_back(x%B); x/=B;} } bigint(string s){ if(s[0]=='-')s.erase(s.begin()),sign=1; int add=0,cnt=0,base=1; while(s.size()){ if(cnt==D){ v.push_back(add); cnt=0; add=0; base=1; } add=(s.back()-'0')*base+add; cnt++; base*=10; s.pop_back(); } if(add)v.push_back(add); } bigint operator-()const{bigint res=*this; res.sign^=1;return res;} bigint abs()const{bigint res=*this; res.sign=0; return res;} ll& operator[](const int i){return v[i];} int size()const{return v.size();} void norm(){ rep(i,0,v.size()-1){ if(v[i]>=0){v[i+1]+=v[i]/B; v[i]%=B;} else{int c=(-v[i]+B-1)/B; v[i]+=c*B; v[i+1]-=c;} } while(!v.empty() and v.back()>=B){ int c=v.back()/B; v.back()%=B; v.push_back(c); } while(!v.empty() and v.back()==0)v.pop_back(); } string to_str()const{ string res; if(v.empty())return "0"; if(sign)res+='-'; res+=to_string(v.back()); for(int i=v.size()-2;i>=0;i--){ string add; int w=v[i]; rep(_,0,D){ add+=('0'+(w%10)); w/=10; } reverse(ALL(add)); res+=add; } return res; } friend istream& operator>>(istream& is,bigint& x){ string tmp; is>>tmp; x=bigint(tmp); return is; } friend ostream& operator<<(ostream& os,bigint x){ os< add(x,0); v.insert(v.begin(),ALL(add)); } return *this; } bigint& operator>>=(const int& x){ v=vector(v.begin()+min(x,(int)v.size()),v.end()); return *this; } bigint& operator+=(const bigint& x){ if(sign!=x.sign){*this-=(-x); return *this;} if((int)v.size()<(int)x.size())v.resize(x.size(),0); rep(i,0,x.size()){v[i]+=x.v[i];} norm(); return *this; } bigint& operator-=(const bigint& x){ if(sign!=x.sign){*this+=(-x); return *this;} if(abs()(b.v.end()-bcur,b.v.end()); pre=inv; inv*=((bigint(2)<<(cur+bcur-1))-inv*c); cur=min(cur<<1,d); inv.v=vector(inv.v.end()-cur,inv.v.end()); } inv.v=vector(inv.v.end()-d,inv.v.end()); bigint res=a*inv; res>>=(a.size()); bigint mul=res*b; while(mul+b<=a){res+=bigint(1); mul+=b;} v=res.v; return *this; } bigint& operator%=(const bigint& x){ bigint div=(*this)/x; (*this)-=div*x; return *this; } bigint square(){ bigint res=*this; res.sign=0; auto v1=FFT::mult(v,v); res.v.assign(v1.size(),0); rep(i,0,v1.size()){ ll val=v1[i]; for(int j=i;val;j++){ if(j==(int)res.v.size())res.v.push_back(0); res.v[j]+=val%B; val/=B; } } res.norm(); return res; } bigint mul(ll x){ bigint res=*this; if(x<0)res.sign^=1,x*=-1; for(int i=res.v.size()-1;i>=0;i--)res.v[i]*=x; res.norm(); return res; } bigint div(ll x){ bigint res=*this; if(x<0)res.sign^=1,x*=-1; for(int i=res.v.size()-1;i>=0;i--){ if(res.v[i]%x!=0 and i!=0){res.v[i-1]+=B*(res.v[i]%x);} res.v[i]/=x; } res.norm(); return res; } bigint operator<<(const int& x)const{return bigint(*this)<<=x;} bigint operator>>(const int& x)const{return bigint(*this)>>=x;} bigint operator+(const bigint& x)const{return bigint(*this)+=x;} bigint operator-(const bigint& x)const{return bigint(*this)-=x;} bigint operator*(const bigint& x)const{return bigint(*this)*=x;} bigint operator/(const bigint& x)const{return bigint(*this)/=x;} bigint operator%(const bigint& x)const{return bigint(*this)%=x;} bool operator<(const bigint& x)const{ if(sign!=x.sign)return sign>x.sign; if((int)v.size()!=(int)x.size()){ if(sign)return (int)x.size()<(int)v.size(); else return (int)v.size()<(int)x.size(); } for(int i=v.size()-1;i>=0;i--)if(v[i]!=x.v[i]){ if(sign)return x.v[i](const bigint& x)const{return x<*this;} bool operator<=(const bigint& x)const{return !(*this>x);} bool operator>=(const bigint& x)const{return !(*thisx);} bool operator!=(const bigint& x)const{return !(*this==x);} }; typedef bigint<4> Bigint; struct Bigfloat{ Bigint v; int p=0; Bigfloat(){} Bigfloat(const ll& _v){v=Bigint(_v);} Bigfloat(const Bigint& _v,int _p=0):v(_v),p(_p){} void set(int _p){if(p<_p){v>>=(_p-p);} else{v<<=(p-_p);} p=_p;} Bigint to_int()const{if(p<0)return v>>(-p); else return v<x.p)set(x.p),v+=x.v; else v+=x.v<<(x.p-p); return *this; } Bigfloat& operator-=(const Bigfloat& x){ if(p>x.p)set(x.p),v-=x.v; else v-=x.v<<(x.p-p); return *this; } Bigfloat square(){Bigfloat res=*this; res.p*=2; res.v=res.v.square(); return res;} Bigfloat mul(ll x){Bigfloat res=*this; res.v=v.mul(x); return res;} Bigfloat div(ll x){Bigfloat res=*this; res.v=v.div(x); return res;} Bigfloat& operator*=(const Bigfloat& x){p+=x.p; v*=x.v; return *this;} Bigfloat& operator/=(const Bigfloat& x){p-=x.p; v/=x.v; return *this;} Bigfloat operator+(const Bigfloat& x)const{return Bigfloat(*this)+=x;} Bigfloat operator-(const Bigfloat& x)const{return Bigfloat(*this)-=x;} Bigfloat operator*(const Bigfloat& x)const{return Bigfloat(*this)*=x;} Bigfloat operator/(const Bigfloat& x)const{return Bigfloat(*this)/=x;} string to_str(){ string res=v.abs().to_str(); int d=Bigint::get_D(); if(p*d>0)res+=string(p*d,'0'); else if(-p*d>=1 and -p*d<(int)res.size()){ res=res.substr(0,(int)res.size()+p*d)+'.'+res.substr((int)res.size()+p*d); } else if(-p*d>=(int)res.size())res="0."+string(-p*d-(int)res.size(),'0')+res; if(v.sign){res.insert(res.begin(),'-');} return res; } friend ostream& operator<<(ostream& os,Bigfloat x){ os< deq; deq.push_back(factor(beg)); while ((*beg) == '*') { beg++; deq.push_back(factor(beg)); } while (deq.size() > 1) { auto x = deq[0]; deq.pop_front(); auto y = deq[0]; deq.pop_front(); deq.push_back(x * y); } return deq[0]; } Bigint factor(State &beg) { if ((*beg) == '(') { beg++; auto ret = expr(beg); beg++; return ret; } else return num(beg); } Bigint num(State &beg) { bool neg = 0; while ((*beg) == '-') { neg ^= 1; beg++; } string buf; while (isdigit(*beg)) { buf += (*beg); beg++; } Bigint ret(buf); if (neg) ret = -ret; return ret; } FastIO io; int main() { int n = 1000000; string s, t; // t = string(49999, '0'); // t[0] = '5'; // s = t + '*' + t; io.read(n, s); State it = s.begin(); auto ret = expr(it); io.write(ret.to_str()); return 0; }