Atcoder Educational DP Contest T - Permutation

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho xâu ~S~ có độ dài ~N - 1~ gồm 2 kí tự <>. Tìm số hoán vị (modulo ~10^9 + 7~) ~P_1, P_2, \dots, P_N~ của ~N~ số nguyên dương đầu tiên thoả mãn với mỗi ~1 \leq i < N~:

  • ~P_i < P_{i + 1}~ nếu kí tự thứ ~i~ trong xâu ~S~ là <.
  • ~P_i > P_{i + 1}~ nếu kí tự thứ ~i~ trong xâu ~S~ là >.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~ (~2 \leq N \leq 3000~).
  • Dòng thứ hai chứa xâu ~S~ độ dài ~N - 1~ chỉ gồm 2 kí tự <>.

Output

In ra số hoán vị thoả mãn điều kiện theo modulo ~10^9 + 7~.

Sample test

Sample Input 1
4
<><
Sample Output 1
5
Giải thích

Có ~5~ hoán vị thoả yêu cầu:

  • ~(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
Giải thích

Có duy nhất ~1~ hoán vị thoả yêu cầu:

  • ~(1,2,3,4,5)~
Sample Input 3
20
>>>><>>><>><>>><<>>
Sample Output 3
217136290
Giải thích

Lưu ý kết quả modulo ~10^9 + 7~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.