Hile and Subsequences' MEX

题号：NC232087
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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$ .

输入描述:

The first line contains an integer  --- the number of test cases.
Each test case is described by one integer  --- the length of the sequence .

输出描述:

Output  lines, each line contains an integer --- the answer modulo .

示例1

输入

复制

2
4
1000000000

输出

复制

15
851104390