#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Prefix Maximum Counting - Repovive Premier Round 6 | Repovive | Repovive

16E. Prefix Maximum Counting

2500 pts2s512 MB

You are given an integer $k$ , a string $s$ of length $n$ consisting only of the characters < and >, and an array $a_1, a_2, \ldots, a_n$ .

Count the number of arrays $x_1, x_2, \ldots, x_n$ such that $1 \le x_i \le k$ for every $i$ , and all of the following conditions are satisfied:

For each $i$ from $1$ to $n$ :

if $s_i$ is <, then $\max(x_1, x_2, \ldots, x_i) < a_i$ .
if $s_i$ is >, then $\max(x_1, x_2, \ldots, x_i) > a_i$ .

Print the answer modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 5 \times 10^5$
$1 \le k \le 3000$
$0 \le a_i \le k+1$
The sum of $n$ over all test cases is at most $5 \times 10^5$ .
The sum of $k$ over all test cases is at most $3000$ .

Input

t

\left. \begin{array}{l} n \quad k \\ s \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \operatorname{ans} \end{array} \right\} \times t

Samples

Input

Case 1

3 4
<><
3 2 5

Case 2

2 3
<<
1 4

Case 3

1 3
>
0

Case 4

3 3
<<<
4 3 2

Case 5

4 3
>><<
0 1 3 4

Explanation

Case 1

The first value can be 1 or 2. The second value must be 3 or 4 to make the second prefix maximum greater than 2. The third value can be any value from 1 to 4, so there are 16 arrays.

Case 2

The first condition asks the first prefix maximum to be less than 1. This is impossible because every chosen value is at least 1.

Case 3

Every chosen value is positive, so the only condition is always satisfied. There are 3 choices.

Case 4

The last condition forces the maximum of all three chosen values to be less than 2. Therefore all chosen values must be 1.

Case 5

Among the first two values, at least one must be 2, and the first three values cannot exceed 2. Then the third value has 2 choices and the last value has 3 choices, so the answer is 18.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given an integer $k$ , a string $s$ of length $n$ consisting only of the characters < and >, and an array $a_1, a_2, \ldots, a_n$ .

Count the number of arrays $x_1, x_2, \ldots, x_n$ such that $1 \le x_i \le k$ for every $i$ , and all of the following conditions are satisfied:

For each $i$ from $1$ to $n$ :

if $s_i$ is <, then $\max(x_1, x_2, \ldots, x_i) < a_i$ .
if $s_i$ is >, then $\max(x_1, x_2, \ldots, x_i) > a_i$ .

Print the answer modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 5 \times 10^5$
$1 \le k \le 3000$
$0 \le a_i \le k+1$
The sum of $n$ over all test cases is at most $5 \times 10^5$ .
The sum of $k$ over all test cases is at most $3000$ .

t

\left. \begin{array}{l} n \quad k \\ s \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \operatorname{ans} \end{array} \right\} \times t

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

16E. Prefix Maximum Counting

Constraints

Input

Output

Samples

16E. Prefix Maximum Counting

Constraints

Input

Output

Samples