#AT20. Permutation
Permutation
Original Problem Statement (English)
Source: AtCoder Educational DP Contest - Problem T
Problem Statement
Let be a positive integer. You are given a string of length , consisting of < and >.
Find the number of permutations of that satisfy the following condition, modulo :
- For each (), if the -th character in is <, and if the -th character in is >.
Constraints
- is an integer.
- is a string of length .
- 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 .
Sample Input 1
4
<><
Sample Output 1
5
There are five permutations that satisfy the condition, as follows:
Sample Input 2
5
<<<<
Sample Output 2
1
There is one permutation that satisfies the condition, as follows:
Sample Input 3
20
>>>><>>><>><>>><<>>
Sample Output 3
217136290
Be sure to print the number modulo .