괄호 넣기

뺄셈은 결합법칙을 만족하지 않는다. 예를 들어 $(5-2)-1 = 2$ 이지만 $5-(2-1) = 4$ 이므로 $(5-2)-1 \neq 5-(2-1)$ 이다. 즉 $5-2-1$ 과 같은 식의 값은 뺄셈을 수행하는 순서에 따라 달라진다. 괄호가 없으면 연산을 왼쪽에서 오른쪽 순서로 계산하므로, $5-2-1$ 은 $(5-2)-1$ 을 뜻한다.

다음과 같은 형태의 식이 주어진다.

$x_1 \pm x_2 \pm \cdots \pm x_n,$

여기서 각 $\pm$ 는 $+$ (더하기) 또는 $-$ (빼기) 중 하나이고, $x_1, x_2, \ldots, x_n$ 은 서로 다른 변수이다.

모두 빼기로만 이루어진 식

$x_1 - x_2 - \cdots - x_n$

에 괄호를 넣어, 주어진 식과 동치인 식을 만들고자 한다. 예를 들어

$x_1 - x_2 - x_3 + x_4 + x_5 - x_6 + x_7$

과 동치인 식을 얻으려면, $x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7$ 에 다음과 같이 괄호를 넣으면 된다.

$(((x_1 - x_2) - ((x_3 - x_4) - x_5)) - (x_6 - x_7)).$

우리는 완전하고 올바르게 괄호가 쳐진 식만 고려한다. 어떤 식이 완전하고 올바르게 괄호가 쳐졌다는 것은 다음 중 하나임을 의미한다.

• 하나의 변수이거나,
• $(w_1 - w_2)$ 꼴이며, 이때 $w_1$ 과 $w_2$ 가 각각 완전하고 올바르게 괄호가 쳐진 식인 경우.

$()$, $(x_i)$, $((\cdots))$ 처럼 불필요한 괄호가 있는 식은 허용하지 않는다. 또한 $x_1 - (x_2 - x_3)$ 은 가장 바깥쪽 괄호가 없으므로 완전하게 괄호가 쳐진 식이 아니다.

주어진 식을 읽고, $x_1 - x_2 - \cdots - x_n$ 에 $n-1$ 쌍의 괄호를 넣어 뺄셈의 순서가 완전히 정해지면서 그 결과가 주어진 식과 동치가 되도록 하는 서로 다른 방법의 수를 $1{,}000{,}000{,}000$ 으로 나눈 나머지로 구하는 프로그램을 작성하라.

첫째 줄에 변수의 개수를 나타내는 정수 $n$ 이 주어진다 ($2 \le n \le 5000$). 다음 $n-1$ 개의 줄에는 각각 문자 $+$ 또는 $-$ 가 하나씩 주어진다. 이 중 $i$ 번째 줄의 문자는 주어진 식에서 $x_i$ 와 $x_{i+1}$ 사이에 있는 연산자이다.

$x_1 - x_2 - \cdots - x_n$ 에 $n-1$ 쌍의 괄호를 넣어 뺄셈의 순서가 완전히 정해지면서 그 결과가 주어진 식과 동치가 되도록 하는 서로 다른 방법의 수를 $1{,}000{,}000{,}000$ 으로 나눈 나머지를 한 줄에 정수 하나로 출력한다.