Юниорская олимпиада по информатике 2021 года за 7 класс | Казахстанские олимпиады

Задача 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]