/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N を正整数とします。
長さ N - 1 の文字列 s が与えられます。
s は < と > からなります。
(1, 2, \ldots, N) を並べ替えた順列 (p_1, p_2, \ldots, p_N) であって、次の条件を満たすものは何通りでしょうか？ 10^9 + 7 で割った余りを求めてください。
- 各 i (1 \leq i \leq N - 1) について、s の i 文字目が
<の場合は p_i < p_{i + 1} であり、s の i 文字目が>の場合は p_i > p_{i + 1} である。
制約
- N は整数である。
- 2 \leq N \leq 3000
- s は長さ N - 1 の文字列である。
- s は
<と>からなる。
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
条件を満たす順列は何通りか？ 10^9 + 7 で割った余りを出力せよ。
入力例 1
4 <><
出力例 1
5
条件を満たす順列は次の 5 通りです。
- (1, 3, 2, 4)
- (1, 4, 2, 3)
- (2, 3, 1, 4)
- (2, 4, 1, 3)
- (3, 4, 1, 2)
入力例 2
5 <<<<
出力例 2
1
条件を満たす順列は次の 1 通りです。
- (1, 2, 3, 4, 5)
入力例 3
20 >>>><>>><>><>>><<>>
出力例 3
217136290
答えを 10^9 + 7 で割った余りを出力することを忘れずに。
Score : 100 points
Problem Statement
Let N be a positive integer.
You are given a string s of length N - 1, consisting of < and >.
Find the number of permutations (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N) that satisfy the following condition, modulo 10^9 + 7:
- For each i (1 \leq i \leq N - 1), p_i < p_{i + 1} if the i-th character in s is
<, and p_i > p_{i + 1} if the i-th character in s is>.
Constraints
- N is an integer.
- 2 \leq N \leq 3000
- s is a string of length N - 1.
- s consists of
<and>.
Input
Input is given from Standard Input in the following format:
N s
Output
Print the number of permutations that satisfy the condition, modulo 10^9 + 7.
Sample Input 1
4 <><
Sample Output 1
5
There are five permutations that satisfy the condition, as follows:
- (1, 3, 2, 4)
- (1, 4, 2, 3)
- (2, 3, 1, 4)
- (2, 4, 1, 3)
- (3, 4, 1, 2)
Sample Input 2
5 <<<<
Sample Output 2
1
There is one permutation that satisfies the condition, as follows:
- (1, 2, 3, 4, 5)
Sample Input 3
20 >>>><>>><>><>>><<>>
Sample Output 3
217136290
Be sure to print the number modulo 10^9 + 7.