H. Three Minimums
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a list of distinct values, we denote with first minimum, second minimum, and third minimum the three smallest values (in increasing order).

A permutation $$$p_1, p_2, \dots, p_n$$$ is good if the following statement holds for all pairs $$$(l,r)$$$ with $$$1\le l < l+2 \le r\le n$$$.

  • If $$$\{p_l, p_r\}$$$ are (not necessarily in this order) the first and second minimum of $$$p_l, p_{l+1}, \dots, p_r$$$ then the third minimum of $$$p_l, p_{l+1},\dots, p_r$$$ is either $$$p_{l+1}$$$ or $$$p_{r-1}$$$.

You are given an integer $$$n$$$ and a string $$$s$$$ of length $$$m$$$ consisting of characters "<" and ">".

Count the number of good permutations $$$p_1, p_2,\dots, p_n$$$ such that, for all $$$1\le i\le m$$$,

  • $$$p_i < p_{i+1}$$$ if $$$s_i =$$$ "<";
  • $$$p_i > p_{i+1}$$$ if $$$s_i =$$$ ">".
As the result can be very large, you should print it modulo $$$998\,244\,353$$$.
Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \leq m \leq \min(100, n-1)$$$).

The second line contains a string $$$s$$$ of length $$$m$$$, consisting of characters "<" and ">".

Output

Print a single integer: the number of good permutations satisfying the constraints described in the statement, modulo $$$998\,244\,353$$$.

Examples
Input
5 3
>>>
Output
5
Input
5 1
<
Output
56
Input
6 5
<<><>
Output
23
Input
10 5
><<><
Output
83154
Input
1008 20
<><<>>><<<<<>>>>>>>>
Output
284142857
Note

In the first test, there are $$$5$$$ good permutations satisfying the constraints given by the string $$$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]$$$. Each of them

  • is good;
  • satisfies $$$p_1 > p_2$$$;
  • satisfies $$$p_2 > p_3$$$;
  • satisfies $$$p_3 > p_4$$$.

In the second test, there are $$$60$$$ permutations such that $$$p_1 < p_2$$$. Only $$$56$$$ of them are good: the permutations $$$[1, 4, 3, 5, 2]$$$, $$$[1, 5, 3, 4, 2]$$$, $$$[2, 4, 3, 5, 1]$$$, $$$[2, 5, 3, 4, 1]$$$ are not good because the required condition doesn't hold for $$$(l, r)$$$ = $$$(1, 5)$$$. For example, for the permutation $$$[2, 4, 3, 5, 1]$$$,

  • the first minimum and the second minimum are $$$p_5$$$ and $$$p_1$$$, respectively (so they are $$$\{p_l, p_r\}$$$ up to reordering);
  • the third minimum is $$$p_3$$$ (neither $$$p_{l+1}$$$ nor $$$p_{r-1}$$$).

In the third test, there are $$$23$$$ good permutations satisfying the constraints given by the string $$$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]$$$.