알록달록한 괄호열

괄호열이란 두 종류의 문자 (또는 )로 이루어진 문자열이다.

좋은 괄호열이란 다음과 같은 규칙을 통해 만들어질 수 있는 괄호열이다.

• 빈 문자열은 좋은 괄호열이다.
• S가 좋은 괄호열이면 (S)도 좋은 괄호열이다. 이 때, S의 양 끝에 붙인 두 괄호는 짝지어졌다고 한다.
• S와 T가 좋은 괄호열이면 ST도 좋은 괄호열이다.

색칠된 괄호열이란 각 괄호가 특정한 색으로 칠해진 괄호열이다.

알록달록한 괄호열이란 다음의 조건을 모두 만족하는 색칠된 괄호열이다.

• 색을 무시하고 괄호의 형태만 봤을 때 좋은 괄호열이다.
• 모든 인접한 두 괄호의 색이 다르다.
• 모든 짝지어진 두 괄호의 색이 다르다.

문자열 $S$에서 하나 이상의 문자를 뽑아 순서대로 나열한 것이 $T$일 때, $S$에서 $T$를 뽑아낼 수 있다고 한다. 

색칠된 괄호열이 주어질 때, 이 괄호열에서 뽑아낼 수 있는 알록달록한 괄호열은 몇 가지일까?

괄호의 형태가 같은 색칠된 괄호열이 여럿 있을 수 있지만 색이 다른 괄호가 하나라도 있으면 다른 경우로 봐야 하며, 문자를 뽑는 방식이 여럿이더라도 결과가 같으면 한 가지 경우로 봐야 한다.

• $P$의 길이를 $N$으로 나타낼 때, $1 \le N \le 700$
• $1 \le |P\[i]| \le N$ (모든 $0 \le i \le N - 1$)