#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; #define FOR(i,l,r) for(ll i=l;i=l;i--) #define RREP(i,n) RFOR(i,0,n) #define ALL(x) x.begin(),x.end() #define PA pair #define F first #define S second #define BS(A,x) binary_search(ALL(A),x) #define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin()) #define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin()) #define COU(A,x) (UB(A,x)-LB(A,x)) #define sz(c) ((ll)(c).size()) /* #include namespace mp=boost::multiprecision; using Bint=mp::cpp_int; */ templateusing min_priority_queue=priority_queue,greater>; templateostream&operator<<(ostream&os,pair&p){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vector&v){REP(i,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b>S; ll N=sz(S); string a="(^^*)",b="(*^^)"; vector>A(N+1,vector(6)),B(N+1,vector(6)); A[0][0]=B[0][0]=1; ll x=0,y=0; REP(i,N){ A[i+1]=A[i]; B[i+1]=B[i]; REP(j,4)if(a[j]==S[i]){A[i+1][j+1]+=A[i][j];if(j)A[i+1][j]-=A[i][j];} REP(j,4)if(b[j]==S[i]){B[i+1][j+1]+=B[i][j];if(j)B[i+1][j]-=B[i][j];} if(S[i]==')'){ x+=A[i][4]; y+=B[i][4]; } } cout<