H. Three Minimumstime limit per test8 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputGiven 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.InputThe 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 ">".OutputPrint a single integer: the number of good permutations satisfying the constraints described in the statement, modulo 998\,244\,353.ExamplesInput
5 3
>>>
Output
5
Input
5 1
<
Output
56
Input
6 5
<<><>
Output
23
Input
10 5
><<><
Output
83154
Input
1008 20
<><<>>><<<<<>>>>>>>>
Output
284142857
NoteIn 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].
5 3
>>>

5 
['combinatorics', 'constructive algorithms', 'divide and conquer', 'dp', 'fft', 'math', '*3500']