Atcoder Educational DP Contest T - Permutation

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.