410648: GYM104068 M 宝可梦与毒瘤 Toxel

Toxel 和 Pikachu 正在与其它宝可梦分享一大块巧克力。这块巧克力是一个 D 维长方体，各维的长度分别为 n₁, n₂, ..., n_D，由 块 1 × 1 × ... × 1 的小正方体巧克力组成。每块小巧克力有一个甜度，不同的块甜度各不相同。不妨将大巧克力放在欧几里得空间的 (0, 0, ..., 0) 至 (n₁, n₂, ..., n_D) 之间的区域，则距原点越近的小巧克力甜度越高。在本题中，你不需要关心甜度的具体数值。

Toxel 喜欢吃甜的巧克力，Pikachu 喜欢吃不甜的巧克力，其它宝可梦则没有特别的要求。现在，Toxel 开始在餐桌上切巧克力了。开始时，桌面上只有那块大巧克力。每次操作，Toxel 会从桌上选择一块可切割的巧克力，即至少有一维长度大于等于 2 的巧克力。设有 d 个维度长度大于等于 2，Toxel 会在每个维度上切一刀，这一刀垂直于该维度的坐标轴，平行于其它维度的坐标轴，且位于整数位置。形式化地说，设待切的巧克力位于 (0, 0, ..., 0) 至 (m₁, m₂, ..., m_d) 之间的区域，切割第 i 维时，Toxel 会选择一个 [1, m_i - 1] 之间的整数 m'_i，使用 x_i = m'_i 这一超平面进行切割。显然，切割后会产生 2^d 块新的巧克力。Toxel 将会把其中平均甜度最高、最低的巧克力块放回餐桌，等待进一步切割。若除这两块巧克力外还有剩余的巧克力，Toxel 和 Pikachu 会把它们分发给其它宝可梦。当餐桌上没有可切割的巧克力块时，Toxel 会先挑走餐桌上最甜的一块巧克力，若还有剩余的巧克力块，Pikachu 会挑走最不甜的一块。若仍有其它巧克力块，Toxel 和 Pikachu 会再将它们分发给其它宝可梦。

宝可梦们喜欢高维空间，因此它们将一块巧克力的价值定义为 ，其中 l_i 是这块巧克力在第 i 维的长度。定义宝可梦们最终的愉悦度为所有宝可梦（包括 Toxel 和 Pikachu）分到的所有巧克力的价值之积。请你求出所有分割方案下的愉悦度之和。两个分割方案不同，当且仅当宝可梦们（包括 Toxel 和 Pikachu）分到的巧克力块组成的集合不同。两个巧克力块相同，当且仅当它们的各维长度对应相等，且在原先的大巧克力块中位于同一位置（切割全过程不允许旋转巧克力块）。

特别地，受到伽勒尔地区能量点的影响，初始的巧克力块可能被缩小。因此 Toxel 希望对于所有 1 ≤ n'₁ ≤ n₁, 1 ≤ n'₂ ≤ n₂, ..., 1 ≤ n'_D ≤ n_D 的 n'₁, n'₂, ..., n'_D 求出大巧克力为 n'₁ × n'₂ × ... × n'_D 时的答案。由于答案很大，你只需要输出答案模 998 244 353 的值。

本题包含多组数据。

第一行包含一个整数 T（1 ≤ T ≤ 2¹⁹），表示数据组数。

对于每组数据：

第一行包含一个整数 D（1 ≤ D ≤ 2¹⁹）。

第二行包含 n 个整数 n₁, n₂, ..., n_D（1 ≤ n_i ≤ 2¹⁹）。保证 。

保证所有数据的 ，保证所有数据的 。

对于每组数据：

输出一行 个整数。大巧克力维度为 n'₁, n'₂, ..., n'_D 的答案输出在第 个整数的位置。

3
1
1
1
2
2
5 5

1
1 1
1 1 1 1 1
1 1 4 10 20
1 8 32 152 592
1 34 388 2806 17384
1 104 3536 51776 514624

注意样例输出的第 3 至 7 行均为第三组数据的输出，实际输出时只需要输出在同一行即可，不需要额外换行。