32346번 - 시큼한 표정

문제

수민이는 문자열을 보며 >< 모양을 시큼한 표정이라고 생각했다. 구체적으로, 수민이가 시큼한 표정이라고 느끼는 문자열은 다음과 같다.

• > 문자가 $k$개, < 문자가 $k$개 연속해서 등장한다. 이때 $k$는 1ドル$ 이상인 양의 정수이다.

위 정의에 따라 >><<, >>><<< 는 모두 시큼한 표정이다. 그러나 ><<<는 >와 <의 개수가 다르고, <>는 괄호의 순서가 옳지 않아 시큼한 표정이 아니다.

수민이는 >와 < 문자로만 이루어진 문자열이 주어졌을 때, 시큼한 표정에 해당하는 문자열만 남겨두고 다른 문자들을 모두 지워버리려고 한다. 하지만 단순한 방법으로 문자를 지우는 것은 재미가 없기에, 승준이는 수민이에게 시큼한 표정을 만들 수 있는 게임을 제안했다.

• 동전을 던져 앞면이 나오면 문자열의 맨 앞 문자를, 뒷면이 나오면 문자열의 맨 뒤 문자를 제거한다.

위 시행을 반복하다가 수민이는 자유롭게 동전 던지기를 종료할 수 있다. 수민이가 동전 던지기를 종료했을 때 문자열이 시큼한 표정이면 승리한다.

길이가 $N$이고 > 와 < 문자로만 이루어진 문자열이 주어졌을 때, 수민이가 게임을 승리하는 경우의 수를 1ドル\ 000\ 000\ 007 (10^9 + 7)$로 나눈 나머지를 구해보자.

입력

첫째 줄에 문자열의 크기 $N$이 주어진다. (1ドル \leq N \leq 2,000円$)

둘째 줄에 >와 < 문자로만 이루어진 길이가 $N$인 문자열 $S$가 주어진다.

출력

게임을 승리하는 동전 던지는 경우의 수를 1ドル\ 000\ 000\ 007 (10^9 + 7)$로 나눈 나머지를 출력한다.

제한

힌트