올바른 괄호 문자열

문자 (, ), [, ], {, }만으로 이루어진 문자열 중 다음 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 한다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. A가 올바른 괄호 문자열이라면 (A), [A], {A}도 올바른 괄호 문자열이다.
3. A와 B가 올바른 괄호 문자열이라면 AB도 올바른 괄호 문자열이다.

예를 들어 [({})], [](){}, [{}]()[{}]는 올바른 괄호 문자열이다. 반면 [({{)[, []({)}, [{}])([{}]는 올바른 괄호 문자열이 아니다.

오래된 종이에 올바른 괄호 문자열이 적혀 있었지만 일부 문자는 알아볼 수 없어 ?로 표시되어 있다. 각 ?를 여섯 가지 괄호 문자 중 하나로 바꾸어 만들 수 있는 올바른 괄호 문자열의 개수를 구하라.

첫째 줄에 문자열의 길이 N이 주어진다. (2 <= N <= 200)

둘째 줄에 길이가 N인 문자열이 주어진다. 알아볼 수 없는 문자는 ?로 표시되어 있다.

만들 수 있는 올바른 괄호 문자열의 개수를 출력한다. 개수가 다섯 자리를 넘으면 마지막 다섯 자리만 출력한다.

첫 번째 공개 테스트에서는 ({([()])}), ()([()]{}), ([([])]{})의 세 문자열을 만들 수 있다.