E-Binary Banter: Counting Combinatorial Bits_福建师范大学第二十二届程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Given a positive integer $n$ , compute the value of the following expression modulo $998244353$ :

$\sum_{i=0}^n\sum_{j=0}^i\left(C_i^j \bmod 2\right)$

Where:

The binomial coefficient $C_i^j$ is defined as:

$C_i^j = \begin{cases} \frac{i!}{j!(i - j)!}, & \text{if } 0 \leq j \leq i \\ 0, & \text{if } j > i \end{cases}$
The factorial $m!$ is defined as the product of all positive integers from $1$ to $m$ :

$m! = \begin{cases} 1, & \text{if } m = 0 \\ 1 \times 2 \times 3 \times \dots \times m, & \text{if } m \geq 1 \end{cases}$
The modulo operation $x \bmod y$ returns the remainder when $x$ is divided by $y$ . For example:

$5 \bmod 2 = 1,\quad 8 \bmod 3 = 2,\quad 7 \bmod 7 = 0$

You need to output the value of the expression modulo $998244353$ .

输入描述:

There are multiple test cases. The first line of the input contains a single integer $t$ $(1 \leq t \leq 3 \times 10^5)$ , denoting the number of test cases. For each test case:

The first and only line contains one integer $n$ $(1 \leq n \leq 10^{18})$ .

输出描述:

For each test case, output one line containing one integer, denoting the value of the expression modulo $998244353$ .

示例1

输入

复制

3
3
5
1145141919810

输出

复制

9
15
516911908

备注:

For the first sample test case, $n = 3$ , so you need to compute the following expression:

$\sum_{i=0}^{3} \sum_{j=0}^{i} \left( C_i^j \bmod 2 \right)$

Let’s analyze each row of binomial coefficients modulo $2$ :

$i = 0$ : $C_0^0 = 1 \Rightarrow 1 \bmod 2 = 1$
$i = 1$ : $C_1^0 = 1$ , $C_1^1 = 1 \Rightarrow 1 + 1 = 2$
$i = 2$ : $C_2^0 = 1$ , $C_2^1 = 2$ , $C_2^2 = 1 \Rightarrow 1 + 0 + 1 = 2$
$i = 3$ : $C_3^0 = 1$ , $C_3^1 = 3$ , $C_3^2 = 3$ , $C_3^3 = 1 \Rightarrow 1 + 1 + 1 + 1 = 4$