Help with interesting problem

Правка en6, от BallBreaker, 2022-10-26 17:38:56

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

Теги permutations

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский 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 Английский BallBreaker 2022-10-26 17:38:28 15
en4 Английский BallBreaker 2022-10-26 17:36:51 88
en3 Английский BallBreaker 2022-10-26 17:33:37 24
en2 Английский BallBreaker 2022-10-26 17:33:11 16
en1 Английский BallBreaker 2022-10-26 17:32:28 1288 Initial revision (published)