Help with interesting problem

Revision en5, by BallBreaker, 2022-10-26 17:38:28

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

Tags permutations

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English BallBreaker 2022-10-26 17:38:56 4 Tiny change: 'put\n\n5\n<><<\n\n' -> 'put\n\n5\n\n\n<><<\n\n'
en5 English BallBreaker 2022-10-26 17:38:28 15
en4 English BallBreaker 2022-10-26 17:36:51 88
en3 English BallBreaker 2022-10-26 17:33:37 24
en2 English BallBreaker 2022-10-26 17:33:11 16
en1 English BallBreaker 2022-10-26 17:32:28 1288 Initial revision (published)