题目描述

有 𝑛 堆果子，分别有 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛 个果子。一次合并分为有顺序的 𝑛 − 1 步，每一步选择两堆果子，合并成一堆。

定义一次合并的权值为每一步被合并的两堆果子数量之积的和。求出每一种合并方法的权值之和对998244353取模的结果。

两种合并方式不同当且仅当有一步被合并的两堆不同。即使有两堆的果子数量相同，我们仍然把它们视为不同的两堆。

输入格式

第一行一个正整数 𝑛。 第二行 𝑛 个非负整数，依次表示 𝑎1 , ⋯ , 𝑎𝑛。

输出格式

一行一个非负整数，表示所有合并方法权值之和（对 998244353 取模）。

样例

样例输入1 2

100001 100002

样例输出1

17856472

样例解释1

只能合并 1 步，即合并仅有的两堆。 两堆果子数量之积为 100001 ∗ 100002 = 10000300002， 对 998244353 取模的结果为 17856472。

注意合并 (𝐴, 𝐵) 和 (𝐵, 𝐴) 视为相同的合并方式。

样例输入2

3

1 2 3

样例输出2

33