괄호 수열

절친 에디 존과 크리스 크로스는 "괄호는 완벽하다" 학회에 참가한다. 두 사람은 학회의 주된 메시지에 전적으로 동의하며, 괄호에 관해 새로 배우는 모든 것에 기뻐한다.

그중 하나가 괄호 수열이다. +와 ×로 계산을 하고 싶을 때는 보통 이렇게 쓴다.

(2 × (2 + 1 + 0 + 1) × 1) + 3 + 2.

괄호는 곱셈과 덧셈을 묶는 데만 쓰인다. 따라서 괄호 밖의 수에는 덧셈이 쓰인다는 것만 기억하면 모든 연산자를 지울 수 있다. 그러면 괄호 수열을 다음과 같이 줄일 수 있다.

( 2 ( 2 1 0 1 ) 1 ) 3 2.

연산자를 모두 쓰지 않아도 되니 훨씬 낫다. 괄호 수열을 읽는 것도 쉽다. 다음 괄호 수열이 있다고 하자.

5 2 ( 3 1 ( 2 2 ) ( 3 3 ) 1 ).

덧셈으로 시작하므로 이는 다음과 같다.

5 + 2 + ( 3 1 ( 2 2 ) ( 3 3 ) 1 ).

괄호는 곱셈을 묶는다는 것을 알고 있으므로 이는 다음과 같다.

5 + 2 + (3 × 1 × ( 2 2 ) × ( 3 3 ) × 1).

그다음 괄호가 한 겹 더 있는데, 이는 곱셈 안의 연산을 묶으므로 그 연산은 덧셈이어야 한다.

5 + 2 + (3 × 1 × (2 + 2) × (3 + 3) × 1) = 5 + 2 + (3 × 1 × 4 × 6 × 1) = 5 + 2 + 72 = 79.

괄호 수열은 연산자가 있는 보통 수식보다 훨씬 쉬우니, 큰 것도 쉽게 계산할 수 있다. 심지어 프로그램을 작성해 계산하게 해 줄 수도 있다.

( )는 올바른 괄호 수열이 아니며, 어떤 올바른 괄호 수열의 부분수열도 아니다.

• 한 줄에 정수 $1 \le n \le 3 \cdot 10^5$가 주어진다.
• 한 줄에 $n$개의 토큰이 주어지며, 각 토큰은 (, ), 또는 정수 $0 \le x < 10^9 + 7$이다. 토큰들은 괄호 수열을 이룬다.

주어진 괄호 수열의 값을 출력한다. 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.