알록달록한 괄호열

괄호열은 (와 ) 두 종류의 문자로 이루어진 문자열이다.

좋은 괄호열은 다음 규칙으로 만들 수 있는 괄호열이다.

• 빈 문자열은 좋은 괄호열이다.
• $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$)