Fantastic Magic Cube

You are given a positive integer $N$ and a set of six-tuples. We define the value of a six-tuple $(l_x, r_x, l_y, r_y, l_z, r_z)$ is $\sum\limits_{l_x \leq x \leq r_x, l_y \leq y \leq r_y, l_z \leq z \leq r_z, }{x \oplus y \oplus z}$. In the beginning, the set has only an element $(0, N - 1, 0, N - 1, 0, N - 1)$. You can do the following steps repeatedly until the size of $S$ equals to $N^3$:

$\bullet$ Pick a six-tuple $(l_x, r_x, l_y, r_y, l_z, r_z)(l_x < r_x \; or \; l_y < r_y \; or \; l_z < r_z)$ from the set.

$\bullet$ You can choose one element of $\left\{ x, y, z \right\} $.

$\space\space\space\space\circ$ Assuming you chose $x$, it must be satisfied that $l_x < r_x$. Then you should pick an integer $t \in [l_x, r_x)$, erase $(l_x, r_x, l_y, r_y, l_z, r_z)$ from the set, add
$\space\space\space\space\space\space$ $(l_x, t, l_y, r_y, l_z, r_z)$ and $(t + 1, r_x, l_y, r_y, l_z, r_z)$ into the set, and you will get the product of values of these two new six-tuples.

$\space\space\space\space\circ$ Assuming you chose $y$, it must be satisfied that $l_y < r_y$. Then you should pick an integer $t \in [l_y, r_y)$, erase $(l_x, r_x, l_y, r_y, l_z, r_z)$ from the set, add
$\space\space\space\space\space\space$ $(l_x, r_x, l_y, t, l_z, r_z)$ and $(l_x, r_x, t + 1, r_y, l_z, r_z)$ into the set, and you will get the product of values of these two new six-tuples.

$\space\space\space\space\circ$ Assuming you chose $z$, it must be satisfied that $l_z < r_z$. Then you should pick an integer $t \in [l_z, r_z)$, erase $(l_x, r_x, l_y, r_y, l_z, r_z)$ from the set, add
$\space\space\space\space\space\space$ $(l_x, r_x, l_y, r_y, l_z, t)$ and $(l_x, r_x, l_y, r_y, t + 1, r_z)$ into the set, and you will get the product of values of these two new six-tuples.

Maximize the sum of values you got and output it modulo $998244353$.

Note that $\oplus$ means exclusive or, for more details refer to https://en.wikipedia.org/wiki/Exclusive_or.

There are multiple test cases.

Each case starts with a line containing one positive integer $N(N \leq 10^6)$.

We guarantee that the sum of $N$s in all test cases is no larger than $3 \times 10^6$.

For each test case, output one line containing an integer denoting the answer.

2

6

2019 Multi-University Training Contest 2