一维坐标轴上的位置 $$$p_1, p_2, \ldots, p_n$$$ 有 $$$n$$$ 个人。最初,对于每个 $$$1 \leq i \leq n$$$,$$$p_i = i$$$。
您可以介绍一些景点 整数 坐标$$$x$$$ ($$$1 \le x \le n$$$),然后所有人都会靠近景点观看。
正式来说,如果您将景点放置在 $$$x$$$ ($$$1 \le x \le n$$$) 位置,则每个人 $$$i$$$ ($$$1 \le i \le n$$$) 都会发生以下变化:
- 如果 $$$p_i = x$$$,则没有变化;
- 如果$$$p_i \lt x$$$,则人向正方向移动,$$$p_i$$$ 增加$$$1$$$;
- 如果$$$p_i \gt x$$$,则该人向负方向移动,并且$$$p_i$$$ 递减$$$1$$$。
您可以按您想要的任意顺序放置任意有限次数的景点。
可以证明,一个人的所有位置始终保持在$$$[1, n]$$$范围内,即$$$1 \le p_i \le n$$$。
每个位置 $$$x$$$ ($$$1 \le x \le n$$$) 都有一个与其关联的值 $$$a_x$$$。位置数组 $$$[p_1, p_2, \ldots, p_n]$$$ 的分数用 $$$score(p)$$$ 表示,为 $$$\sum_{i = 1}^{n} a_{p_i}$$$,即最后每站在 $$$x$$$ 处的人,你的分数就会增加 $$$a_x$$$。
在放置景点时可能出现的所有可能的不同位置数组 $$$p$$$ 中,找到 $$$score(p)$$$ 的总和。由于答案可能很大,因此打印它对 $$$998\,244\,353$$$ 取模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 — $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含一个整数:$$$score(p)$$$ 在所有可能的不同位置数组 $$$p$$$ 上的总和,这些数组可能与放置景点有关,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
71125 1031 1 141 1 1 1410 2 9 751000000000 1000000000 1000000000 1000000000 10000000008100 2 34 59 34 27 5 6
输出复制
145247248033357293069365
注意
在第一个测试用例中,唯一可能的结果是该人 $$$1$$$ 停留在 $$$1$$$。其得分为 $$$a_1 = 1$$$。
在第二个测试用例中,以下位置数组 $$$[p_1, p_2]$$$ 是可能的:
- $$$[1, 2]$$$,得分$$$15$$$;
- $$$[1, 1]$$$,得分 $$$10$$$;
- $$$[2, 2]$$$,得分 $$$20$$$。
分数总和为 $$$15 + 10 + 20 = 45$$$。
在第三个测试用例中,以下位置数组 $$$[p_1, p_2, p_3]$$$ 是可能的:
- $$$[1, 1, 1]$$$;
- $$$[1, 1, 2]$$$;
- $$$[1, 2, 2]$$$;
- $$$[1, 2, 3]$$$;
- $$$[2, 2, 2]$$$;
- $$$[2, 2, 3]$$$;
- $$$[2, 3, 3]$$$;
- $$$[3, 3, 3]$$$.
每个人的得分为 $$$3$$$,因此总和为 $$$24$$$。