#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; typedef long double LD; typedef double D; typedef pair P; typedef pair PD; typedef map M; #define vp(c,n) vec c(n);rep(i,n){c[i]=i;} #define out(x) cout<= (n); --i) #define drep(i, n) drep2(i, n, 0) #define REP(i, n) FOR(i, 0, n) #define fore(i,a) for(const auto &i:a) #define RREP(var, n) for (auto var = n - 1; var != static_cast(-1); var--)//なんですかこれは #define all(x) (x).begin(),(x).end() #define memset(v, h) memset((v), h, sizeof(v)) #define frac(x) x-floor(x) #define eb emplace_back #define pb push_back #define pbd(x,y) push_back({x,y}); #define pbt(x,y,z) push_back({x,y,z}); #define bs binary_search #define lb lower_bound #define ub upper_bound #define SUM(x) accumulate(all(x),0) #define IP(a,b) inner_product(all(a),begin(b),0.0)//内積の計算 #define PS(a,b) partial_sum(all(a),begin(b))//累積和(具体的にはbは個数以外空にしておいて格納されていく) #define uni(x) sort(all(x));x.erase(unique(all(x)),x.end()) //重複消去&sort #define fr(f,x) fixed<,greater

> #define PQS PQ> #define fi first//大文字になれない #define se second #define cauto const auto& #define bit(n) (1LL<<(n)) #define cl clock()/CLOCKS_PER_SEC//時間計測 #define printd(n,x) cout<>a[i];}//試験運転してみる(多分つかわない) #define cinvv(a,n,m); rep(i,n){rep(j,m){cin>>a[i][j];}} template inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;} template inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;} typedef vector vec; typedef vector ves; typedef vector mat; //const ll mod = 1000000009;//手動で切り替える. //const ll mod = 998244353; const ll mod = 1000000007; //const ll mod=1e9; using mint =modint998244353;//.val()が必要に注意 一旦置いておく //using mint =modint1000000009; //using mint =modint1000000007; const ll INF = bit(60); //ll dx[4]={0,1,0,-1},dy[4]={-1,0,1,0}; //struct Edge{ll to,co;Edge(ll to=0,ll co=0):to(to),co(co){}};//ABC191で何となくsunukeさんの!! //struct Edge {ll to;ll cost;}; //struct Edge {ll from;ll to;ll cost;}; //struct Edge {ll to;ll w;Edge(ll to,ll w):to(to),w(w){}}; //けんちょん本 G[頂点a].pb(Edge(頂点b,weight));とか //using Graph = vector>; //struct Edge {ll to,t,k;Edge(ll to,ll t,ll k):to(to),t(t),k(k){}};//ABC192で何となく //using Graph =vector>; #define cing(a,b,c) a[b].pb(c);a[c].pb(b); //vector seen; //void gdfs(const Graph &G,ll v){seen[v]=true;fore(next_v,G[v]){if(seen[next_v])continue;gdfs(G,next_v);}}//それぞれの点でif(seen[i])continue;else gdfs(G,i)をする ll modpow(ll a,ll n,ll mod){if(mod==1)return 0;ll ret=1;ll p=a%mod;while(n){if(n&1)ret=ret*p%mod;p=p*p%mod;n>>=1;}return ret; } M factor(ll n) {M ret;for(ll i=2;i*i<=n;i++){while(n%i==0){ret[i]++;n /= i;}}if(n != 1){ret[n]=1;}return ret;}//素因数分解 mapにする vec divisor(ll n){vec K;for(ll i=1;i*i<=n;i++){if(n%i==0){K.pb(i);if(i*i!=n)K.pb(n/i);}}sort(all(K));return K;}//約数列挙 cauto& a=divisor(100);的に書く ll modlog(ll a,ll b,ll p){ll g=1;for(ll i=p;i;i/=2)(g*=a)%=p;g=gcd(g,p);ll t=1,c=0;for(;t%g;c++){if(t==b)return c;(t*=a)%=p;}if(b%g){return -1;}t/=g;b /= g;ll n=p/g,h=0,gs=1;for(;h*hbs;for(ll s=0,e=b;s(NdN2, my_div(N, x2) + 1);ll ix = x;for (ll i = 1; i < imax; ++i) {hl[i] -= (ix < NdN2 ? hl[ix] : hs[my_div(N, ix)]) - pi;ix += x;}for (int n = N2; n >= x2; n--) {hs[n] -= hs[my_div(n, x)] - pi;}++pi;}return hl[1];} // /* constexpr ll MAX = 3000000;ll fac[MAX],finv[MAX],inv[MAX];//int main(){cominit();}と打つのを忘れないように. void cominit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;iT phi(T n) {T ret=n;for(T i = 2; i * i <= n; i++){if(n % i == 0){ret -= ret / i;while(n % i == 0) n /= i;}}if(n > 1){ret -= ret / n;}return ret;} templateT extgcd(T a, T b, T &x, T &y){T d = a;if(b != 0){d=extgcd(b,a%b,y,x);y -= (a / b) * x;}else {x = 1;y = 0;}return d;} mat mat_mul(mat&a,mat&b){mat res(a.size(),vec(b[0].size()));rep(i,a.size()){rep(j,b[0].size()){rep(k,b.size()){(res[i][j]+=a[i][k]*b[k][j])%=mod;}}}return res;} mat matpow(mat a,ll n){mat res(a.size(),vec(a.size()));rep(i,a.size())res[i][i]=1;while(n>0){if(n & 1)res=mat_mul(a,res);a=mat_mul(a,a);n>>=1;}return res;} #define cinmat(a,x,y) mat a(x,vec(y));rep(i,x)rep(j,y)cin>>a[i][j];//;をつけなくていいよ!(お気持ちかなり使いやすそう使いにくかったらやめるけども) #define comat(a,x,y) rep(i,x){rep(j,y){cout< //fw(n);としてfw.add(p,x)->fw[p]+x fw.sum(l,r)->Σ[l,r-1]fw[i] (O(logn)!!) #define SA(s) vec suffix_arry(s)//よくわかんない #define LCP(s,a) vec lcp_rray(s,a)//Long Common Prefix #define ZA(s) z_algorithm(s)//上と同じようなやつ #define IV(x,m) inv_mod(x,m)//逆元がなんと対応!! //ついでに pair crt(r,m) 解なし(0,0) n=0 (0,1) CRT!! #define FS(n,m,a,b) floor_sum(n,m,a,b)//Σ[0,n-1]floor((a*i+b)/m) (これがなんとO(log(max(n,m,a,b)))) #define FFT(a,b,c) vec a=convolution(b,c)//FFT,NNT 畳み込み をFFT()の直後に挿入したらmodできる. void ACC(vec a,vec &b){b[0]=0;rrep(i,a.size()){b[i]=b[i-1]+a[i-1];}return;} //幾何ライブラリの構築をする!! using Point = complex; const D EPS = 1e-7; const D PI = acosl(-1); inline bool equal(const D &a, const D &b) { return fabs(a - b) < EPS; } Point unitVector(const Point &a) { return a / abs(a); }//単位vec Point normalVector(const Point &a) { return a * Point(0, 1); }//法線vec D dot(const Point &a, const Point &b) {return (a.real() * b.real() + a.imag() * b.imag());}//内積 D cross(const Point &a, const Point &b) {return (a.real() * b.imag() - a.imag() * b.real());}//外積 Point rotate(const Point &p, const D &theta) {return Point(cos(theta) * p.real() - sin(theta) * p.imag(),sin(theta) * p.real() + cos(theta) * p.imag());}//pを反時計周りにtheta回転 D radianToDegree(const D &radian) { return radian * 180.0 / PI; }//ラジアン->度 D degreeToRadian(const D °ree) { return degree * PI / 180.0; }//度->ラジアン int ccw(const Point &a, Point b, Point c) {b-= a,c-=a;if(cross(b,c)>EPS){return 1;}if(cross(b,c)<-EPS){return -1;}if(dot(b,c)<0){return 2;}if(norm(b) c1.r + c2.r + EPS){return 4;}if(equal(d, c1.r + c2.r)){return 3;}if(equal(d, abs(c1.r - c2.r))){return 1;}if(d < abs(c1.r - c2.r) - EPS){return 0;}return 2;}//{(2つの円が離れている場合),(外接している場合),(内接している場合),(内包している場合)} 2つの円の交差判定(返り値は共通接線の数) vector crossPoint(const Circle &c1, const Circle &c2) {vector res;int mode = isIntersect(c1, c2);D d = abs(c1.p - c2.p);if(mode == 4){return res;}if(mode == 0){return res;}if(mode == 3) {D t = c1.r / (c1.r + c2.r);res.emplace_back(c1.p + (c2.p - c1.p) * t);return res;}if(mode == 1) {if(c2.r < c1.r - EPS) {res.emplace_back(c1.p + (c2.p - c1.p) * (c1.r / d));} else {res.emplace_back(c2.p + (c1.p - c2.p) * (c2.r / d));}return res;}D rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);D rs1 = sqrt(c1.r * c1.r - rc1 * rc1);if(c1.r - abs(rc1) < EPS){rs1 = 0;}Point e12 = (c2.p - c1.p) / abs(c2.p - c1.p);res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, 1));res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, -1));return res;}//2つの円の交点 bool isInCircle(const Circle &c, const Point &p) {D d = abs(c.p - p);return (equal(d, c.r) || d < c.r - EPS);}//点pが円cの内部(円周上も含む)に入っているかどうか vector crossPoint(const Circle &c, const Line &l) {vector res;D d = distanceBetweenLineAndPoint(l, c.p);if(d > c.r + EPS) {return res;}Point h = projection(l, c.p);if(equal(d, c.r)) {res.emplace_back(h);return res;}Point e = unitVector(l.b - l.a);D ph = sqrt(c.r * c.r - d * d);res.emplace_back(h - e * ph);res.emplace_back(h + e * ph);return res;}//円cと直線lの交点 vector tangentToCircle(const Point &p, const Circle &c) {return crossPoint(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));}//点pを通る円cの接線(2本あるので、接点のみを返す) vector tangent(const Circle &a, const Circle &b) {vector ret;D g = abs(a.p - b.p);if(equal(g, 0)){return ret;}Point u = unitVector(b.p - a.p);Point v = rotate(u, PI / 2);for(int s : {-1, 1}) {D h = (a.r + b.r * s) / g;if(equal(h * h, 1)) {ret.emplace_back(a.p + (h > 0 ? u : -u) * a.r,a.p + (h > 0 ? u : -u) * a.r + v);} else if(1 - h * h > 0) {Point U = u * h, V = v * sqrt(1 - h * h);ret.emplace_back(a.p + (U + V) * a.r,b.p - (U + V) * (b.r * s));ret.emplace_back(a.p + (U - V) * a.r,b.p - (U - V) * (b.r * s));}}return ret;}//円の共通接線 D PolygonArea(const vector &p) {D res = 0;int n = p.size();for(int i = 0; i < n - 1; i++) res += cross(p[i], p[i + 1]);res += cross(p[n - 1], p[0]);return res * 0.5;}//多角形の面積を求める bool isConvex(const vector &p) {int n = p.size();int now, pre, nxt;for(int i = 0; i < n; i++) {pre = (i - 1 + n) % n;nxt = (i + 1) % n;now = i;if(ccw(p[pre], p[now], p[nxt]) == -1){return false;}}return true;}//凸多角形かどうか vector ConvexHull(vector p) {int n = (int)p.size(), k = 0;sort(all(p), [](const Point &a, const Point &b) {return (real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b));});vector ch(2 * n);for(int i = 0; i < n; ch[k++] = p[i++]) { while(k >= 2 &&cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)--k;}for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {while(k >= t &&cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)--k;}ch.resize(k - 1);return ch;}//凸包 O(NlogN) int isContained(const vector &g, const Point &p) {bool in = false;int n = (int)g.size();for(int i = 0; i < n; i++) {Point a = g[i] - p, b = g[(i + 1) % n] - p;if(imag(a) > imag(b)){swap(a, b);}if(imag(a) <= EPS && EPS < imag(b) && cross(a, b) < -EPS){in = !in;}if(cross(a, b) == 0 && dot(a, b) <= 0) return 1;}return (in ? 2 : 0);}//多角形gに点pが含まれているか(含まれる:2,辺上にある:1,含まれない:0) vector ConvexCut(vector p, Line l) {vector ret;int sz = (int)p.size();rep(i, sz){Point now = p[i];Point nxt = p[i == sz-1 ? 0 : i+1];if(ccw(l.a, l.b, now) != -1) ret.emplace_back(now);if(ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0) {ret.emplace_back(crossPoint(Line(now, nxt), l));}}return ret;}//凸多角形pを直線lで切断し、その左側を返す struct Barrett { using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; u32 m; u64 im; Barrett() : m(), im() {} Barrett(int n) : m(n), im(u64(-1) / m + 1) {} constexpr inline i64 quo(u64 n) { u64 x = u64((__uint128_t(n) * im) >> 64); u32 r = n - x * m; return m <= r ? x - 1 : x; } constexpr inline i64 rem(u64 n) { u64 x = u64((__uint128_t(n) * im) >> 64); u32 r = n - x * m; return m <= r ? r + m : r; } constexpr inline pair quorem(u64 n) { u64 x = u64((__uint128_t(n) * im) >> 64); u32 r = n - x * m; if (m <= r) return {x - 1, r + m}; return {x, r}; } constexpr inline i64 pow(u64 n, i64 p) { u32 a = rem(n), r = m == 1 ? 0 : 1; while (p) { if (p & 1) r = rem(u64(r) * a); a = rem(u64(a) * a); p >>= 1; } return r; } }; struct prime_power_binomial { int p, q, M; vector fac, ifac, inv; int delta; Barrett bm, bp; prime_power_binomial(int _p, int _q) : p(_p), q(_q) { assert(1 < p && p <= ((1LL << 30) - 1)); assert(_q > 0); long long m = 1; while (_q--) { m *= p; assert(m <=((1LL << 30) - 1)); } M = m; bm = Barrett(M), bp = Barrett(p); enumerate(); delta = (p == 2 && q >= 3) ? 1 : M - 1; } void enumerate() { int MX = min(M, 20000000 + 10); fac.resize(MX); ifac.resize(MX); inv.resize(MX); fac[0] = ifac[0] = inv[0] = 1; fac[1] = ifac[1] = inv[1] = 1; for (int i = 2; i < MX; i++) { if (i % p == 0) { fac[i] = fac[i - 1]; fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1)); i++; } else { fac[i] = bm.rem(1LL * fac[i - 1] * i); } } ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1); for (int i = MX - 2; i > 1; --i) { if (i % p == 0) { ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1)); ifac[i - 1] = ifac[i]; i--; } else { ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1)); } } } long long Lucas(long long n, long long m) { int res = 1; while (n) { int n0, m0; tie(n, n0) = bp.quorem(n); tie(m, m0) = bp.quorem(m); if (n0 < m0) return 0; res = bm.rem(1LL * res * fac[n0]); int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]); res = bm.rem(1LL * res * buf); } return res; } long long C(long long n, long long m) { if (n < m || n < 0 || m < 0) return 0; if (q == 1) return Lucas(n, m); long long r = n - m; int e0 = 0, eq = 0, i = 0; int res = 1; while (n) { res = bm.rem(1LL * res * fac[bm.rem(n)]); res = bm.rem(1LL * res * ifac[bm.rem(m)]); res = bm.rem(1LL * res * ifac[bm.rem(r)]); n = bp.quo(n); m = bp.quo(m); r = bp.quo(r); int eps = n - m - r; e0 += eps; if (e0 >= q) return 0; if (++i >= q) eq += eps; } if (eq & 1) res = bm.rem(1LL * res * delta); res = bm.rem(1LL * res * bm.pow(p, e0)); return res; } }; struct binomial_mod { int mod; vector M; vector cs; binomial_mod(long long md) : mod(md) { assert(1 <= md); assert(md <= ((1LL << 30) - 1)); for (int i = 2; i * i <= md; i++) { if (md % i == 0) { int j = 0, k = 1; while (md % i == 0) md /= i, j++, k *= i; M.push_back(k); cs.emplace_back(i, j); assert(M.back() == cs.back().M); } } if (md != 1) { M.push_back(md); cs.emplace_back(md, 1); } assert(M.size() == cs.size()); } long long C(long long n, long long m) { if (mod == 1) return 0; vector rem, d; for (int i = 0; i < (int)cs.size(); i++) { rem.push_back(cs[i].C(n, m)); d.push_back(M[i]); } return crt(rem, d).first; } }; int main(){ string t; cin>>t; bool k=true; ll kk=0; rep(i,t.size()){ if(t[i]=='('){k=false;} if(k){cout<