Prefix Painting - Repovive Standard Round 7 | Repovive

22C. Prefix Painting

1500 pts2s256 MB

You have a strip of $n$ cells, numbered from $1$ to $n$ . Initially, all cells are uncolored.

There are $n$ painting instructions. Instruction $i$ paints cells $1$ through $i$ with color $c_i$ , overwriting their previous colors.

You must execute every instruction exactly once, in any order you choose.

How many different final colorings can you obtain? Output the answer modulo $998244353$ .

Two colorings are different if at least one cell has a different color.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le c_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, output the number of different final colorings modulo $998244353$ on a separate line.

Samples

Input

Case 1

1
1

Case 2

3
1 2 1

Explanation

Case 1

The only instruction paints the only cell with color 1. There is exactly one final coloring.

Case 2

The possible final colorings are (1, 1, 1), (1, 2, 1), and (2, 2, 1). For example, executing instructions 3, 2, 1 in that order produces (1, 2, 1).

Output

Case 1

Case 2

Input

Case 1

4
3 3 3 3

Case 2

3
1 2 3

Case 3

4
1 2 1 2

Explanation

Case 1

Every instruction uses color 3, so the final coloring is always (3, 3, 3, 3).

Case 2

The possible final colorings are (1, 2, 3), (2, 2, 3), (1, 3, 3), and (3, 3, 3).

Case 3

The possible final colorings are (1, 1, 1, 2), (1, 2, 1, 2), (2, 2, 1, 2), (1, 2, 2, 2), and (2, 2, 2, 2).

Output

Case 1

Case 2

Case 3

You have a strip of $n$ cells, numbered from $1$ to $n$ . Initially, all cells are uncolored.

There are $n$ painting instructions. Instruction $i$ paints cells $1$ through $i$ with color $c_i$ , overwriting their previous colors.

You must execute every instruction exactly once, in any order you choose.

How many different final colorings can you obtain? Output the answer modulo $998244353$ .

Two colorings are different if at least one cell has a different color.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le c_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, output the number of different final colorings modulo $998244353$ on a separate line.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

22C. Prefix Painting

Constraints

Input

Output

Samples

22C. Prefix Painting

Constraints

Input

Output

Samples