Prefix Maximum Counting - Repovive Premier Round 6 | 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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16E. Prefix Maximum Counting

Constraints

Input

Output

Samples

16E. Prefix Maximum Counting

Constraints

Input

Output

Samples