Age Reports - Repovive Standard Round 7 | Repovive

22E. Age Reports

2500 pts2s256 MB

There are $n$ people, numbered from $1$ to $n$ . Each person's age is an integer between $1$ and $m$ , inclusive. Several people may have the same age.

Each person counts the people who are strictly younger than them and the people who are strictly older than them, then reports the smaller of these two counts. Person $i$ reports $a_i$ .

Find the number of possible assignments of ages consistent with all the reports, modulo $998244353$ .

Two assignments are different if at least one person's age is different. If no assignment is consistent with all the reports, the answer is $0$ .

Constraints

$1 \le t \le 10^4$
$1 \le n, m \le 2 \times 10^5$
$0 \le a_i < n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

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

Output

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

Here, $ans$ is the number of consistent age assignments modulo $998244353$ .

Samples

Input

Case 1

2 3
0 0

Case 2

3 3
0 1 0

Explanation

Case 1

With only two people, neither person can have both a younger person and an older person. Every assignment is valid, so there are 3 * 3 = 9 assignments.

Case 2

The possible age sequences, in person order, are (1, 2, 3) and (3, 2, 1). In both sequences, person 2 has one younger person and one older person, while each other person has nobody on one side of their age.

Output

Case 1

Case 2

Input

Case 1

4 3
0 0 1 1

Case 2

3 2
0 1 0

Case 3

5 5
0 0 0 2 2

Explanation

Case 1

The possible age sequences are (1, 3, 2, 2) and (3, 1, 2, 2). Each of people 3 and 4 has exactly one younger person and one older person.

Case 2

Person 2 needs both a strictly younger person and a strictly older person. This requires at least three different ages, but only ages 1 and 2 are available.

Case 3

A person reporting 2 must have at least two younger people and at least two older people. With five people in total, nobody else can have the same age as this person. Thus each person reporting 2 would have to be the unique middle person in age order, which cannot hold for both people 4 and 5.

Output

Case 1

Case 2

Case 3

There are $n$ people, numbered from $1$ to $n$ . Each person's age is an integer between $1$ and $m$ , inclusive. Several people may have the same age.

Each person counts the people who are strictly younger than them and the people who are strictly older than them, then reports the smaller of these two counts. Person $i$ reports $a_i$ .

Find the number of possible assignments of ages consistent with all the reports, modulo $998244353$ .

Two assignments are different if at least one person's age is different. If no assignment is consistent with all the reports, the answer is $0$ .

$1 \le t \le 10^4$
$1 \le n, m \le 2 \times 10^5$
$0 \le a_i < n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

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

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

Here, $ans$ is the number of consistent age assignments modulo $998244353$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

22E. Age Reports

Constraints

Input

Output

Samples

22E. Age Reports

Constraints

Input

Output

Samples