T820179 A305

题目背景

by tjh

Kevin 作为机房内最巨的 P 话哥，决定带领 A305 的蒟蒻一起 P。

题目描述

A305 机房内有 $n$ 个人，从左到右每个人的 P 话程度为 $A=(a_1,a_2,\dots, a_n)$。

Kevin 定义一个有 $n$ 个人的机房 $A$ 内人的 $P^0$ 话程度为 $\min(A)\times n$。

Sandom 认为 $P^0$ 太容易求了，所以定义 $P^1$ 话程度为机房的所有子区间（包括机房本身）的 $P^0$ 话程度的和。

BennyT 依然认为 $P^1$ 太容易求了，所以定义 $P^k$ 话程度为机房的所有子区间（包括机房本身）的 $P^{k-1}$ 话程度的和。

现在 nsp 大手子想要知道 A305 的 $P^k$ 话程度。

形式化题意

对于一个长度为 $n$ 的正整数序列 $A=(a_1,a_2\dots a_n)$，定义：

$$f_k(A) = \begin{cases} \min(A)\times len(A) & k=0 \\ f_k(A)=\sum_{A'为A的子区间}f_{k-1}(A') & k>0 \end{cases}$$

求 $f_k(A)$。

输入格式

第一行两个整数 $n,k$，$n$ 表示 A305 的人数。

第二行 $n$ 个整数，表示 A305 的人的 P 话程度 $A$。

输出格式

输出 A305 的 $P^k$ 话程度对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

5 1
4 1 3 2 5

输出 #1

52

输入输出样例 #2

输入 #2

5 2
4 1 3 2 5

输出 #2

216

输入输出样例 #3

输入 #3

5 114
114 321 123 222 456

输出 #3

791997751

输入输出样例 #4

输入 #4

7 114514
11451419 99824435 31415926 88888888 1000000000 999999999 87654321

输出 #4

207043104

说明/提示

由于本题输入量较大，请选手使用较快的读入方式。

样例解释 #1

当 $k=1$ 时，$P^1$ 话程度为序列 $A$ 所有子区间的 $P^0$ 话程度之和。 对于子区间 $A[l\dots r]$，其 $P^0$ 话程度为 $\min(A[l..r]) \times (r-l+1)$。

序列 $A=(4,1,3,2,5)$，长度为 $5$，共有 $\frac{5 \times 6}{2} = 15$ 个子区间。逐一计算如下：

子区间	元素	$\min$	长度	$P^0 = \min \times len$
$[1,1]$	$\{4\}$	4	1	4
$[1,2]$	$\{4,1\}$	1	2
$[1,3]$	$\{4,1,3\}$		3
$[1,4]$	$\{4,1,3,2\}$		4
$[1,5]$	$\{4,1,3,2,5\}$		5
$[2,2]$	$\{1\}$		1
$[2,3]$	$\{1,3\}$		2
$[2,4]$	$\{1,3,2\}$		3
$[2,5]$	$\{1,3,2,5\}$		4
$[3,3]$	$\{3\}$	3	1	3
$[3,4]$	$\{3,2\}$	2	2	4
$[3,5]$	$\{3,2,5\}$		3	6
$[4,4]$	$\{2\}$		1	2
$[4,5]$	$\{2,5\}$		2	4
$[5,5]$	$\{5\}$	5	1	5

将所有 $P^0$ 值求和：$4+2+3+4+5+1+2+3+4+3+4+6+2+4+5 = 52$

故 $P^1$ 话程度为 $52$。

对于 $5\%$ 的数据，满足 $1 \le n,k \le 15$。

对于另外 $10\%$ 的数据，满足 $k=1$。

对于另外 $15\%$ 的数据，满足 $1 \le n,k \le 1000$。

对于另外 $10\%$ 的数据，满足 $1 \le n,k \le 10000$。

对于另外 $50\%$ 的数据，满足 $1 \le n,k \le 10^5$。

对于 $100\%$ 的数据，满足 $1 \le n \le 3\times 10^6,1 \le k \le 10^9,1 \le a_i \le 10^9$。