區間最小值總和問題
給你一個長度為 $N$ 的正整數數列 $(A_1, A_2, A_3, ... , A_N)$，定義 $\text{MIN(S)}$ 代表一個集合 $S$ 裡面最小的那個值，例如 : $\text{MIN}(1,3,4) = 1$，想請你求所有數對 $(l, r)$ 符合 $1 ≤ l ≤ r ≤ N$ 的 $\text{MIN}(A_l, A_{l+1}, ... , A_r)$ 的總和，也就是請你求以下的東西 :
$\sum_{l=1}^N \sum_{r=l}^N \text{MIN}(A_l, A_{l+1}, ... , A_r)$
以上是 r1cky 想到的問題，但他覺得有點太簡單，所以他把它改成了以下的題目 :
很多區間最小值總和問題
給予兩個正整數 $N, M$，代表所有長度為 $N$ 的正整數數列 $(A_1, A_2, A_3, ... , A_N)$ 符合 $ 1 ≤ A_i ≤ M (1 ≤ i ≤ N)$，總共有 $M^N$ 個滿足此條件且相異的數列，請你求這 $M^N$ 個數列對於 區間最小值總和問題 的答案總和，因為答案可能很大，請模 $998244353$。
解決 很多區間最小值總和問題 。
輸入有一行，代表兩個正整數 $N, M$，中間以空格隔開。
- $ 1 ≤ N, M ≤ 2 \times 10^5$
輸出答案模 $998244353$。
2 2
17
20 10
982045350
31415 48763
502635375
不公開 測資點#0 (5%): 2.0s , <1K
不公開 測資點#1 (5%): 2.0s , <1K
不公開 測資點#2 (5%): 2.0s , <1K
不公開 測資點#3 (5%): 2.0s , <1K
不公開 測資點#4 (5%): 2.0s , <1K
不公開 測資點#5 (5%): 2.0s , <1K
不公開 測資點#6 (5%): 2.0s , <1K
不公開 測資點#7 (5%): 2.0s , <1K
不公開 測資點#8 (5%): 2.0s , <1K
不公開 測資點#9 (5%): 2.0s , <1K
不公開 測資點#10 (5%): 2.0s , <1K
不公開 測資點#11 (5%): 2.0s , <1K
不公開 測資點#12 (5%): 2.0s , <1K
不公開 測資點#13 (5%): 2.0s , <1K
不公開 測資點#14 (5%): 2.0s , <1K
不公開 測資點#15 (5%): 2.0s , <1K
不公開 測資點#16 (5%): 2.0s , <1K
不公開 測資點#17 (5%): 2.0s , <1K
不公開 測資點#18 (5%): 2.0s , <1K
不公開 測資點#19 (5%): 2.0s , <1K
範例輸入 # 1
以下為了方便解釋，我們定義 $F(X)$ 代表序列 $X$ 對於 區間最小值總和問題 的答案，並且我們對於每個可能的序列進行以下分析 :
當 $(N, M) = (2, 2)$ 時，序列有可能是 $(1, 1),\ (1, 2),\ (2, 1),\ (2, 2)$ 這 $4$ 種。
$A = (1, 1)$，$F(A) = \text{MIN}(1) + \text{MIN}(1) + \text{MIN}(1, 1) = 1 + 1 + 1 = 3$。
$A = (1, 2)$，$F(A) = \text{MIN}(1) + \text{MIN}(2) + \text{MIN}(1, 1) = 1 + 2 + 1 = 4$。
$A = (2, 1)$，$F(A) = \text{MIN}(2) + \text{MIN}(1) + \text{MIN}(2, 1) = 2 + 1 + 1 = 4$。
$A = (2, 2)$，$F(A) = \text{MIN}(2) + \text{MIN}(2) + \text{MIN}(2, 2) = 2 + 2 + 2 = 6$。
所以 $\sum F(A) = 3 + 4 + 4 + 6 = 17$ ，答案為 $17$。
範例輸入 # 2 & 3
請記得將答案模 $998244353$。
Authored by r1cky