시큼한 표정
시간 제한1초메모리 제한1024 MB
양끝에서 문자를 제거하는 동전 던지기를 멈췄을 때 남는 부분 문자열이 '>' k개와 '<' k개가 되도록 하는 경우의 수를 센다.
문제
수민이는 문자열을 보며 >< 모양을 시큼한 표정이라고 생각했다. 구체적으로, 수민이가 시큼한 표정이라고 느끼는 문자열은 다음과 같다.
- > 문자가 개, < 문자가 개 연속해서 등장한다. 이때 는 이상인 양의 정수이다.
위 정의에 따라 >><<, >>><<< 는 모두 시큼한 표정이다. 그러나 ><<<는 >와 <의 개수가 다르고, <>는 괄호의 순서가 옳지 않아 시큼한 표정이 아니다.
수민이는 >와 < 문자로만 이루어진 문자열이 주어졌을 때, 시큼한 표정에 해당하는 문자열만 남겨두고 다른 문자들을 모두 지워버리려고 한다. 하지만 단순한 방법으로 문자를 지우는 것은 재미가 없기에, 승준이는 수민이에게 시큼한 표정을 만들 수 있는 게임을 제안했다.
- 동전을 던져 앞면이 나오면 문자열의 맨 앞 문자를, 뒷면이 나오면 문자열의 맨 뒤 문자를 제거한다.
위 시행을 반복하다가 수민이는 자유롭게 동전 던지기를 종료할 수 있다. 수민이가 동전 던지기를 종료했을 때 문자열이 시큼한 표정이면 승리한다.
길이가 이고 > 와 < 문자로만 이루어진 문자열이 주어졌을 때, 수민이가 게임을 승리하는 경우의 수를 로 나눈 나머지를 구해보자.
입력
첫째 줄에 문자열의 크기 이 주어진다. ()
둘째 줄에 >와 < 문자로만 이루어진 길이가 인 문자열 가 주어진다.
출력
게임을 승리하는 동전 던지는 경우의 수를 로 나눈 나머지를 출력한다.