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
<
andif the
-th character in
is
>
.
Constraints
is an integer.
is a string of length
.
consists of
<
and>
.
Input Specification
The first line will contain the integer .
The second line will contain the string .
Output Specification
Print the number of permutations that satisfy the condition, modulo .
Note: Be sure to print the number modulo .
Sample Input 1
4
<><
Sample Output 1
5
Explanation For Sample 1
There are five permutations that satisfy the condition, as follows:
Sample Input 2
5
<<<<
Sample Output 2
1
Explanation For Sample 2
There is one permutation that satisfies the condition, as follows:
Sample Input 3
20
>>>><>>><>><>>><<>>
Sample Output 3
217136290
Comments