최고의 괄호 문자열

최근 소들은 균형 잡힌 괄호 문자열로 경쟁하며 누구의 문자열이 가장 좋은지 서로 비교하고 있습니다.

균형 잡힌 괄호 문자열의 점수는 다음 규칙으로 정해집니다(아래에서 다루는 모든 문자열은 균형 잡혀 있습니다).

• 문자열 ()의 점수는 $1$입니다.
• 문자열 A의 점수가 $s(A)$이면, (A)의 점수는 $2 \cdot s(A)$입니다.
• 문자열 A와 B의 점수가 각각 $s(A)$, $s(B)$이면, 이 둘을 이어 붙인 AB의 점수는 $s(A) + s(B)$입니다.

예를 들어 $s(\text{(())()}) = s(\text{(())}) + s(\text{()}) = 2 \cdot s(\text{()}) + 1 = 2 \cdot 1 + 1 = 3$입니다.

Bessie는 다른 모든 소를 이기고 싶어 하므로 주어진 문자열의 점수를 계산할 수 있어야 합니다. 길이가 $N$($2 \le N \le 100{,}000$)인 균형 잡힌 괄호 문자열이 주어질 때, 그 점수를 구하세요.

• 첫째 줄: 정수 $N$ 하나.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 문자열의 $i$번째 문자를 나타내는 정수 하나가 주어집니다. 그 문자가 (이면 $0$, )이면 $1$입니다.

• 첫째 줄: 문자열의 점수. 이 값이 매우 커질 수 있으므로 $12345678910$으로 나눈 나머지를 출력합니다.

입력은 문자열을 한 문자씩 인코딩한 것입니다. 각 값에서 $0$은 여는 괄호 (를, $1$은 닫는 괄호 )를 의미합니다. 이 값들을 순서대로 이어 붙여 원래 괄호 문자열을 복원한 뒤 점수 규칙을 적용하면 됩니다.