Задача A. Перестановки
| Ограничение по времени | Ограничение по памяти |
|---|---|
| 1 секунда | 256 мегабайт |
У Султана была перестановка чисел от 1 до N. Для интереса он расставил между соседними числами перестановки знаки неравенства ">" и "<". Например если перестановка была [1, 3, 2, 5, 4], то получится [1<3>2<5>4]. Он устал от игр со своей перестановкой и отлучился сделать себе смузи из манго. Пока Султан делал смузи в комнату пришла его кошка и стерла все числа, но знаки неравенства остались. Теперь Султану интересно сколько существует перестановок удовлетворяющих этим неравенствам. Так как способов может быть очень много он попросил вас помочь ему и дать ему ответ по модулю 998244353.
Перестановка чисел длины N - это массив из N целых чисел, где каждое число от 1 до N встречается ровно 1 раз. Например [1 2 3] и [4 2 1 3] являются перестановками, а [1 2 2] и [1 2 3 5] не являются.
Формат входного файла
Первая строка содержит целое число N (1≤N≤2000) длина перестановки. Вторая строка содержит строку из N-1 символов "<" или ">".
Формат выходного файла
Выведите количество перестановок по модулю 998244353.
Система оценки
| N ≤ 10 | 19 баллов |
| N ≤ 20 | 30 баллов |
| N ≤ 500 | 22 баллов |
| N ≤ 2000 | 29 баллов |
Примеры
Входные данные
3
><
Выходные данные
2
Входные данные
5
<<<<<
Выходные данные
1
Примечание
В первом тесте подходят перестановки [2 1 3] и [3 1 2]. Во втором тесте подходит только [1 2 3 4 5]