올바른 괄호 문자열
시간 제한1초메모리 제한128 MB
물음표를 여섯 종류의 괄호 문자 중 하나로 채워서 올바른 괄호 문자열을 만드는 방법의 수를 마지막 다섯 자리까지 구합니다.
문제
문자 (, ), [, ], {, }만으로 이루어진 문자열 중 다음 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 한다.
- 빈 문자열은 올바른 괄호 문자열이다.
A가 올바른 괄호 문자열이라면(A),[A],{A}도 올바른 괄호 문자열이다.A와B가 올바른 괄호 문자열이라면AB도 올바른 괄호 문자열이다.
예를 들어 [({})], [](){}, [{}]()[{}]는 올바른 괄호 문자열이다. 반면 [({{)[, []({)}, [{}])([{}]는 올바른 괄호 문자열이 아니다.
오래된 종이에 올바른 괄호 문자열이 적혀 있었지만 일부 문자는 알아볼 수 없어 ?로 표시되어 있다. 각 ?를 여섯 가지 괄호 문자 중 하나로 바꾸어 만들 수 있는 올바른 괄호 문자열의 개수를 구하라.
입력
첫째 줄에 문자열의 길이 N이 주어진다. (2 <= N <= 200)
둘째 줄에 길이가 N인 문자열이 주어진다. 알아볼 수 없는 문자는 ?로 표시되어 있다.
출력
만들 수 있는 올바른 괄호 문자열의 개수를 출력한다. 개수가 다섯 자리를 넘으면 마지막 다섯 자리만 출력한다.
힌트
첫 번째 공개 테스트에서는 ({([()])}), ()([()]{}), ([([])]{})의 세 문자열을 만들 수 있다.