CF1654H Three Minimums

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

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