时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的序列 $a = (a_1, a_2, \dots, a_n)$。

我们将序列 $a$ 重复复制 $k$ 次，得到一个长度为 $nk$ 的新序列 $X$。

具体地，$X_{(m \cdot n) + i} = a_i$，其中 $0 \le m < k, 1 \le i \le n$。

定义“三元逆序对”为满足以下条件的三元组 $(i, j, k)$：

1. $1 \le i < j < k \le nk$
2. $X_i > X_j > X_k$

计算序列 $X$ 中三元逆序对的总数。由于答案很大，请输出对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含两个正整数 $n$ 和 $k$，分别表示序列 $a$ 的长度和重复次数。

第二行包含 $n$ 个正整数 $a_1 ,a_2 ,a_3 ,\cdots, a_n$，表示序列 $a$ 的值。

输出格式

输出一个整数，表示三元逆序对的总数对 $998244353$ 取模后的值。

样例

样例输入 #1

3 2
3 2 1

样例输出 #1

4

样例解释 #1

对应的数组为：$X = [3, 2, 1, 3, 2, 1]$。

满足条件的逆序对为 : $(1,2,3),(1,2,6),(1,5,6),(4,5,6)$。

样例输入 #2

3 3
1 2 3

样例输出 #2

1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$k \le$	$n\le$
$1$	$30$	$10$	$300$
$2$	$50$	$10^6$
$3$	$20$		$2000$

对于 $100 \%$ 的数据，$3 \le n \le 2000$，$1 \le k \le 10^6$，$1 \le a_i \le 2000$。