You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

兔子国的 Tom 正在加工种出来的胡萝卜，他买了 $n$ 瓶增长药剂，每瓶药剂的功效可能不同，药剂的功效用序列 $a_1,a_2,\cdots,a_n$ 表示。

他有 $n$ 根胡萝卜，它们的大小分别是 $1,2,\cdots,n$，他先把他的 $n$ 根胡萝卜随机打乱并排成一排，每根的大小用排列 $p_1,p_2,\cdots,p_n$ 来表示，然后对第 $i$ 根胡萝卜使用第 $i$ 瓶药剂，之后第 $i$ 根胡萝卜的大小 $p_i$ 会变成 $p_i \times a_i$。

Tom 喜欢整齐的升序排列的胡萝卜，一个胡萝卜序列的不整齐度定义为其逆序对数量，他想知道喷洒完药剂后序列 $p$ 的不整齐度是多少，由于他是随机打乱的，因此对于 $p$ 的所有 $n!$ 种情况，你要计算每种情况的不整齐度之和，答案可能很大，请输出对 $998244353$ 取模的结果。

对于一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，如果一对下标 $(i,j)$ 满足 $1 \le i < j \le n$ 且 $a_i > a_j$，则称这对下标 $(i,j)$ 构成了序列的一个逆序对。

输入格式

第一行包含一个整数 $n$，表示胡萝卜数量及药剂数量。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示 $n$ 瓶药剂的功效。

输出格式

一行一个整数，表示每种情况喷洒完药剂后序列的不整齐度之和，输出对 $998244353$ 取模的结果。

样例

样例输入 1

3
1 2 1

样例输出 1

8

样例输入 2

4
2 3 1 2

样例输出 2

74

数据范围

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10$。