1006. 开关灯

题目描述

小 D 很喜欢随机性。他面前有一排 n 盏灯，从左到右编号为 1, 2, …, n，第 i 盏灯的权值为 ai。一开始，所有灯都是关闭的。

小 D 随机选择一个 1 ∼ n 的排列，并按照这个排列依次打开所有灯。每打开一盏灯后，所有亮着的灯会形成若干个极大连续段。若当前共有 c 个连续段，并且这次打开的是第 i 盏灯，那么小 D 会获得 ai ⋅ c

分。小 D 想知道，最终总得分的期望是多少？答案对 998 244 353 取模。

输入格式

本题有多组测试数据。第一行输入一个正整数 T (1 ≤ T ≤ 2 × 105 )，表示测试数据组数。接下来输入 T 组测试数据。每组测试数据包含两行：第一行一个整数 n (1 ≤ n ≤ 2 × 105 )。第二行 n 个整数 a1, a2, …, an (0 ≤ ai < 998 244 353)。

保证单个测试点内所有测试数据的 n 之和不超过 2 × 106。

输出格式

输出一个整数，表示小 D 最终总得分的期望值对 998 244 353 取模后的结果。可以证明答案是一个分母不被 998 244 353 整除的有理数。若答案最简表示为 xy，你需要输出 x × y −1 mod 998 244 353，其中 y −1 表示 y

在模 998 244 353 意义下的乘法逆元。

样例输入

2
1
10
3
1 2 3

样例输出

10
665496242

提示

本题输入量较大，建议使用较快速的输入方式（如关闭流同步的cin）。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）