codeforces#P1654H. Three Minimums

Three Minimums

Description

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$.

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 ">".

Print a single integer: the number of good permutations satisfying the constraints described in the statement, 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$.

Samples

5 3
&gt;&gt;&gt;
5
5 1
&lt;
56
6 5
&lt;&lt;&gt;&lt;&gt;
23
10 5
&gt;&lt;&lt;&gt;&lt;
83154
1008 20
&lt;&gt;&lt;&lt;&gt;&gt;&gt;&lt;&lt;&lt;&lt;&lt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;
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]$.