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 \lt 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 \lt p_{i+1}$ if $s_i =$ "<";
• $p_i \gt 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$.

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 \gt p_2$;
• satisfies $p_2 \gt p_3$;
• satisfies $p_3 \gt p_4$.

In the second test, there are $60$ permutations such that $p_1 \lt 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]$.