P10329 [UESTCPC 2024] Add

Given a sequence $a_1, a_2, \ldots, a_n$ of length $n$, initially $a_i = i$. Perform $n - 1$ operations on this sequence. In the $i$-th operation, choose an integer $j$ uniformly at random from $[1, n - i]$, and set $a_j$ to $a_j + 2a_{n - i + 1}$. After all operations are finished, compute the expected value of $a_1 \bmod\text{ }998244353$.

The first line contains a positive integer $T$ $(1 \leq T \leq 10^4)$, the number of test cases. The next $T$ lines each contain a positive integer $n$ $(1 \leq n \leq 10^9)$, representing the length of the sequence.

Output $T$ lines. Each line contains one integer, the expected value of $a_1 \bmod\text{ }998244353$.

Translated by ChatGPT 5