P10128 "Daily OI Round 3" Xor Graph

Before dawn arrives, someone must light up the darkness.

Xs_siqi gives you $2^n$ vertices. There is a **directed** edge from $x$ to $y$ if and only if $x \operatorname{xor} y = 2^k$, $k \in [0,n)$, and $x > y$. Here, $\operatorname{xor}$ means bitwise XOR, and $k$ is an integer. Let $f_{x,y}$ be the number of different paths from vertex $x$ to vertex $y$. Find: $$\sum_{i=1}^{2^n}\sum_{j=1}^{2^n}f_{i,j}(i\neq j)$$ Output the answer modulo $998244353$.

The first line contains an integer $t$. The next $t$ lines (lines $2$ to $t+1$) each contain an integer $n$.

Output $t$ lines. Each line contains an integer representing the number of valid paths required by the problem.

#### Sample Explanation #1 For the first test case of the sample, vertex $3$ has edges to $1$ and $2$. Then there is one path from $3$ to $1$ and one path from $3$ to $2$, for a total of $2$ paths. #### Constraints For all testdata: $1 \le t \le 10^6$, $1 \le n \le 10^7$. Translated by ChatGPT 5