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$$$.
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$$$,
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$$$.
5 3 >>>
5
5 1 <
56
6 5 <<><>
23
10 5 ><<><
83154
1008 20 <><<>>><<<<<>>>>>>>>
284142857
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
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]$$$,
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]$$$.
Name |
---|