H. Три минимума
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для набора различных чисел мы называем первым минимумом, вторым минимумом и третьим минимумом три наименьших значения (в возрастающем порядке).

Перестановка $$$p_1, p_2, \dots, p_n$$$ называется хорошей, если для всех пар $$$(l,r)$$$, удовлетворяющих $$$1\le l < l+2 \le r\le n$$$, выполняется следующее условие.

  • Если $$$\{p_l, p_r\}$$$ являются (не обязательно в таком порядке) первым и вторым минимумами среди $$$p_l, p_{l+1}, \dots, p_r$$$, то третий минимум среди $$$p_l, p_{l+1},\dots, p_r$$$ это либо $$$p_{l+1}$$$, либо $$$p_{r-1}$$$.

Вам дано целое число $$$n$$$ и строка $$$s$$$ длины $$$m$$$, состоящая из символов «<» и «>».

Вычислите количество хороших перестановок $$$p_1, p_2,\dots, p_n$$$ таких, что для всех $$$1\le i\le m$$$,

  • $$$p_i < p_{i+1}$$$, если $$$s_i =$$$ «<»;
  • $$$p_i > p_{i+1}$$$, если $$$s_i =$$$ «>».
Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \leq m \leq \min(100, n-1)$$$).

Вторая строка содержит строку $$$s$$$ длины $$$m$$$, состоящую из символов «<» и «>».

Выходные данные

Выведите одно целое число: количество хороших перестановок, удовлетворяющих ограничениям из условия, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
5 3
>>>
Выходные данные
5
Входные данные
5 1
<
Выходные данные
56
Входные данные
6 5
<<><>
Выходные данные
23
Входные данные
10 5
><<><
Выходные данные
83154
Входные данные
1008 20
<><<>>><<<<<>>>>>>>>
Выходные данные
284142857
Примечание

В первом примере существуют $$$5$$$ хороших перестановок, удовлетворяющих условиям, задаваемым строкой $$$s$$$: $$$[4, 3, 2, 1, 5]$$$, $$$[5, 3, 2, 1, 4]$$$, $$$[5, 4, 2, 1, 3]$$$, $$$[5, 4, 3, 1, 2]$$$, $$$[5, 4, 3, 2, 1]$$$. Каждая из них

  • хорошая;
  • удовлетворяет $$$p_1 > p_2$$$;
  • удовлетворяет $$$p_2 > p_3$$$;
  • удовлетворяет $$$p_3 > p_4$$$.

Во втором примере существуют $$$60$$$ перестановок таких, что $$$p_1 < p_2$$$. Только $$$56$$$ из них хорошие: перестановки $$$[1, 4, 3, 5, 2]$$$, $$$[1, 5, 3, 4, 2]$$$, $$$[2, 4, 3, 5, 1]$$$, $$$[2, 5, 3, 4, 1]$$$ не являются хорошими, потому что необходимое условие не выполнено для $$$(l, r)$$$ = $$$(1, 5)$$$. Например, для перестановки $$$[2, 4, 3, 5, 1]$$$,

  • первый и второй минимумы — это $$$p_5$$$ и $$$p_1$$$ соответственно (то есть $$$\{p_l, p_r\}$$$ с точностью до порядка);
  • третий минимум $$$p_3$$$ (то есть ни $$$p_{l+1}$$$, ни $$$p_{r-1}$$$).

В третьем примере есть $$$23$$$ хорошие перестановки, удовлетворяющие ограничениям строки $$$s$$$: $$$[1, 2, 4, 3, 6, 5]$$$, $$$[1, 2, 5, 3, 6, 4]$$$, $$$[1, 2, 6, 3, 5, 4]$$$, $$$[1, 3, 4, 2, 6, 5]$$$, $$$[1, 3, 5, 2, 6, 4]$$$, $$$[1, 3, 6, 2, 5, 4]$$$, $$$[1, 4, 5, 2, 6, 3]$$$, $$$[1, 4, 6, 2, 5, 3]$$$, $$$[1, 5, 6, 2, 4, 3]$$$, $$$[2, 3, 4, 1, 6, 5]$$$, $$$[2, 3, 5, 1, 6, 4]$$$, $$$[2, 3, 6, 1, 5, 4]$$$, $$$[2, 4, 5, 1, 6, 3]$$$, $$$[2, 4, 6, 1, 5, 3]$$$, $$$[2, 5, 6, 1, 4, 3]$$$, $$$[3, 4, 5, 1, 6, 2]$$$, $$$[3, 4, 5, 2, 6, 1]$$$, $$$[3, 4, 6, 1, 5, 2]$$$, $$$[3, 4, 6, 2, 5, 1]$$$, $$$[3, 5, 6, 1, 4, 2]$$$, $$$[3, 5, 6, 2, 4, 1]$$$, $$$[4, 5, 6, 1, 3, 2]$$$, $$$[4, 5, 6, 2, 3, 1]$$$.