409354: GYM103488 H Hile and Subsequences' MEX
Description
Before we start, we need to declare a few definitions.
MEX
$$$MEX$$$ of a sequence is the smallest non-negative integer doesn't appears in the sequence. For example:
- $$$MEX$$$ of $$$[1,2,3,4]$$$ is $$$0$$$.
- $$$MEX$$$ of $$$[0,1,2,3,4]$$$ is $$$5$$$.
- $$$MEX$$$ of $$$[2,3,4,0,2]$$$ is $$$1$$$.
Subsequence
The sequence $$$b$$$ is a subsequence of the sequence $$$a$$$ if and only if it can be obtained by deleting zero or more elements in $$$a$$$ without changing the order of the remaining elements. For example:
- $$$[1,2,3,4]$$$ is a subsequence of of $$$[1,2,3,4]$$$
- $$$[1,4]$$$ is a subsequence of of $$$[1,2,3,4]$$$
- $$$[4,1]$$$ is not a subsequence of of $$$[1,2,3,4]$$$
Hile has a sequence $$$a$$$ with length of $$$n(n \leq 10^9)$$$. The $$$i$$$-th element of $$$a$$$ is $$$i-1$$$ (i.e. $$$a=[0,1,2\dots n-1]$$$). Please help Hile calculate the sum of $$$MEX$$$ of all subsequences of $$$a$$$.
Since the answer may be very large, please output the answer modulo $$$998244353$$$.
InputThe first line contains an integer $$$t(1\le t \leq 10^5)$$$ — the number of test cases.
Each test case is described by one integer $$$n(1\le n\le 10^9)$$$ — the length of the sequence $$$a$$$.
OutputOutput $$$t$$$ lines, each line contains an integer — the answer modulo $$$998244353$$$.
ExampleInput2 4 1000000000Output
15 851104390