$B$ を正の整数からなる長さ $M$ の配列とします。
1 回の操作では、添字の空でない部分列$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$ であって、対応する値 $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ が互いに異なるものを選び、選んだ各値を $1$ ずつ減らすことができます。
$B$ のスコア $\text{score}(B)$ を、$B$ のすべての要素を $0$ にするために必要な最小の操作回数として定義します。
長さ $N$ の配列 $A$ が与えられます。
$A$ のすべての空でない部分列にわたるスコアの総和を求めてください。
値は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。
$^\dagger$ 列 $C$ が列 $D$ の部分列であるとは、$D$ からいくつか(0 個またはすべてでもよい)の要素を、残りの要素の順序を変えずに削除することで得られることをいいます。
入力
入力は以下の形式で与えられます:
T N A_1 A_2 ... A_N :
- 入力される値はすべて整数である。
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- すべてのテストケースにおける $N^2$ の総和は $5000^2$ を超えないことが保証される。
出力
各テストケースについて、1 つの整数 — $A$ のすべての空でない部分列にわたるスコアの総和を $998\,244\,353$ で割った余り — を出力してください。
入出力例
入力例 1
3 1 5 3 1 1 3 4 2 2 2 2
出力例 1
5 16 47
注記
テストケース 1: 唯一の空でない部分列は $[5]$ であり、そのスコアは $5$ です。したがって、答えは $5$ です。
テストケース 2: $[1, 1, 3]$ の空でない部分列は以下の通りです:
- $[1]$ に等しい 2 つの部分列(それぞれのスコアは $1$)、
- $[3]$(スコアは $3$)、
- $[1, 1]$(スコアは $2$)、
- $[1, 3]$ に等しい 2 つの部分列(それぞれのスコアは $3$)、
- $[1, 1, 3]$(スコアは $3$)。
したがって、総和は $16$ です。