Expected Beauty - Repovive Premier Round 4 | Repovive

9F. Expected Beauty

3250 pts2s256 MB

You are given an array $a_1, a_2, \ldots, a_n$ .

You perform the following operation exactly $k$ times.

Choose two integers $l$ and $r$ uniformly at random among all pairs satisfying $1 \le l \le r \le n$ , then reverse the subarray $a_l, a_{l+1}, \ldots, a_r$ .

The operations are independent.

The beauty of an array $b$ is defined as

\sum_{1 \le x < y \le n} \max(0, b_x - b_y).

Compute the expected value of the beauty of the final array modulo $998244353$ .

Formally, if the expected value can be written as an irreducible fraction $\frac{p}{q}$ , output $p \times q^{-1}$ modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^6$
The sum of $n$ over all test cases is at most $10^6$
$0 \le k \le 10^9$
$1 \le a_i \le 10^9$

Input

t

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

Output

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

Samples

Input

Case 1

1 100
7

Case 2

2 0
5 2

Case 3

2 1
5 2

Case 4

3 1
3 1 2

Case 5

10 3
10 1 9 2 8 3 7 4 6 5

Explanation

Case 1

The array has only one element, so the beauty is always $0$ .

Case 2

No operation is performed, so the beauty remains $3$ .

Case 3

There are $3$ possible segments, and the expected beauty is $2$ .

Case 4

After one operation, the expected beauty is $\frac{5}{2}$ .

Case 5

This is a larger sample with $n=10$ and $k=3$ .

Output

Case 1

Case 2

Case 3

Case 4

499122179

Case 5

969444607

You are given an array $a_1, a_2, \ldots, a_n$ .

You perform the following operation exactly $k$ times.

Choose two integers $l$ and $r$ uniformly at random among all pairs satisfying $1 \le l \le r \le n$ , then reverse the subarray $a_l, a_{l+1}, \ldots, a_r$ .

The operations are independent.

The beauty of an array $b$ is defined as

\sum_{1 \le x < y \le n} \max(0, b_x - b_y).

Compute the expected value of the beauty of the final array modulo $998244353$ .

Formally, if the expected value can be written as an irreducible fraction $\frac{p}{q}$ , output $p \times q^{-1}$ modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 10^6$
The sum of $n$ over all test cases is at most $10^6$
$0 \le k \le 10^9$
$1 \le a_i \le 10^9$

t

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

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

The array has only one element, so the beauty is always $0$ .

No operation is performed, so the beauty remains $3$ .

There are $3$ possible segments, and the expected beauty is $2$ .

After one operation, the expected beauty is $\frac{5}{2}$ .

This is a larger sample with $n=10$ and $k=3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9F. Expected Beauty

Constraints

Input

Output

Samples

9F. Expected Beauty

Constraints

Input

Output

Samples