Fly Me to the Moon - Repovive Goodbye 2025 Round | Repovive

1F. Fly Me to the Moon

3000 pts4s256 MB

Sam and AmShZ had always dreamed of Flying to the Moon, but as you might guess, this dream had never come true. When Santa Claus noticed their wish, he tried to help them, but he himself was facing a serious problem delivering gifts all around the world. So Sam and AmShZ decided to help Santa Claus, and in return Santa would fulfill their wish. Now Santa Claus asks Sam and AmShZ to place the gifts into his sleigh to reduce some of his workload. Sam and AmShZ act as follows:

If they receive $k$ gifts from Santa with weights $b_1,b_2, \ldots, b_k$ , in order to reduce the weight of the sleigh, they discard some of them (possibly none, possibly all) and put the rest into the sleigh. More precisely, they choose a subset $S$ of the numbers from $1$ to $k$ , and the gifts whose indices are in $S$ are placed into the sleigh.

They define the complexity of an array $b$ of gifts as the smallest non-negative integer $x$ such that, for every possible way Sam and AmShZ choose some gifts, sum of weights of gifts inside sleigh is not equal to $x$ . they denote this value (complexity of the array) by $F(b)$ . (note that sum of weights of an empty set $S$ of gifts is 0).

On the other hand, Santa Claus has $n$ gifts in his warehouse with weights $a_1,a_2,..,a_n$ . but he has not yet decided which ones to give to Sam and AmShZ. However, he is certain that he will choose a contiguous subarray of the gifts.

Now, in order to have an estimate of how difficult the gifts they will receive might be, Sam and AmShZ ask you to compute the sum of the complexities of all contiguous subarrays of the gifts in Santa Claus’s warehouse, and output it modulo $998244353$ .

Actually, you should output following value modulo $998244353$ :

\sum_{l=1}^{n} \sum_{r=l}^{n} F([a_l, a_{l+1}, \ldots, a_r])

Constraints

$1 \le t \le 200$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \\ 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

3
1 5 2

Case 2

4
1 2 3 4

Case 3

8
4 1 1 1 14 2 27 4

Explanation

$F([1]) = 2$ .

$F([1,5]) = 2$ (Because Sam and AmShZ can choose empty subset for total weight $0$ , and only first gift for total weight $1$ , but they can't choose a subset with total weight $2$ ).

$F([1,5,2]) = 4$ .

$F([5]) = 1$ .

$F([5,2]) = 1$ .

$F([2]) = 1$ .

So we have $2 + 2 + 4 + 1 + 1 + 1 = 11$ .

Output

Case 1

Case 2

Case 3

Actually, you should output following value modulo $998244353$ :

\sum_{l=1}^{n} \sum_{r=l}^{n} F([a_l, a_{l+1}, \ldots, a_r])

Constraints

$1 \le t \le 200$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \\ 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

$F([1]) = 2$ .

$F([1,5]) = 2$ (Because Sam and AmShZ can choose empty subset for total weight $0$ , and only first gift for total weight $1$ , but they can't choose a subset with total weight $2$ ).

$F([1,5,2]) = 4$ .

$F([5]) = 1$ .

$F([5,2]) = 1$ .

$F([2]) = 1$ .

So we have $2 + 2 + 4 + 1 + 1 + 1 = 11$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1F. Fly Me to the Moon

Input

Output

Samples

1F. Fly Me to the Moon

Constraints

Input

Output

Samples

Constraints