Problem statement:↵
_The Sultan had a permutation of numbers from 1 to N. For interest, he put inequality signs ">" and "<" between adjacent permutation numbers. For example, if the permutation was [1, 3, 2, 5, 4], then it would be [1<3>2<5>4]. He got tired of playing with his swap and went to make himself a mango smoothie. While the Sultan was preparing a smoothie, his cat entered the room and erased all the numbers, but the inequality signs remained. Now the Sultan is interested in how many permutations exist that satisfy these inequalities._↵
_Since there can be many ways, he asked you to help him and give an answer modulo 998244353._↵
__↵
↵
↵
_A permutation of numbers of length N is an array of N integers, where each number from 1 to N occurs exactly 1 time. For example, [1 2 3] and [4 2 1 3] are permutations, but [1 2 2] and [1 2 3 5] are not._↵
__↵
↵
↵
_Input_↵
_The first line contains an integer N — the length of the permutation. The second line contains a string of N-1 characters "<" or ">"._↵
↵
↵
_Output_↵
_Print the number of permutations modulo 998244353._↵
↵
↵
↵
↵
↵
So there some subtasks↵
↵
↵
n<=10 — 10 points↵
↵
↵
n<=20 — 10 points↵
↵
↵
n<=500 — 30 points↵
↵
↵
n<=2000 — 60 points↵
↵
↵
↵
Examples:↵
↵
Input↵
↵
5↵
>>>><><<↵
↵
↵
Output↵
↵
↵
9↵
↵
↵
Input↵
↵
3↵
↵
<>↵
↵
Output↵
↵
2↵
↵
↵
↵
I already have idea for first subtask using n! solution↵
↵
_The Sultan had a permutation of numbers from 1 to N. For interest, he put inequality signs ">" and "<" between adjacent permutation numbers. For example, if the permutation was [1, 3, 2, 5, 4], then it would be [1<3>2<5>4]. He got tired of playing with his swap and went to make himself a mango smoothie. While the Sultan was preparing a smoothie, his cat entered the room and erased all the numbers, but the inequality signs remained. Now the Sultan is interested in how many permutations exist that satisfy these inequalities._↵
_Since there can be many ways, he asked you to help him and give an answer modulo 998244353._↵
__↵
↵
↵
_A permutation of numbers of length N is an array of N integers, where each number from 1 to N occurs exactly 1 time. For example, [1 2 3] and [4 2 1 3] are permutations, but [1 2 2] and [1 2 3 5] are not._↵
__↵
↵
↵
_Input_↵
_The first line contains an integer N — the length of the permutation. The second line contains a string of N-1 characters "<" or ">"._↵
↵
↵
_Output_↵
_Print the number of permutations modulo 998244353._↵
↵
↵
↵
↵
↵
So there some subtasks↵
↵
↵
n<=10 — 10 points↵
↵
↵
n<=20 — 10 points↵
↵
↵
n<=500 — 30 points↵
↵
↵
n<=2000 — 60 points↵
↵
↵
↵
Examples:↵
↵
Input↵
↵
5↵
↵
↵
Output↵
↵
↵
9↵
↵
↵
Input↵
↵
3↵
↵
<>↵
↵
Output↵
↵
2↵
↵
↵
↵
I already have idea for first subtask using n! solution↵
↵
