## Educational DP Contest AtCoder T - Permutation

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 1G

Problem type

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 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