Misalkan $B$ adalah sebuah larik dengan panjang $M$ yang terdiri dari bilangan-bilangan bulat positif.
Dalam satu operasi, Anda boleh memilih sebuah upabarisan tak kosong$^\dagger$ dari indeks $1 \le i_1 < i_2 < \dots < i_k \le M$ sedemikian sehingga nilai-nilai $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ saling berbeda, lalu mengurangi setiap nilai yang dipilih sebesar $1$.
Definisikan skor dari $B$, yang dinyatakan dengan $\text{score}(B)$, sebagai banyaknya operasi minimum yang diperlukan untuk membuat setiap elemen dari $B$ sama dengan $0$.
Anda diberikan sebuah larik $A$ dengan panjang $N$.
Carilah jumlah skor dari semua upabarisan tak kosong dari $A$.
Karena nilainya mungkin besar, keluarkan hasilnya modulo $998\,244\,353$.
$^\dagger$ Sebuah barisan $C$ disebut upabarisan dari barisan $D$ jika barisan tersebut dapat diperoleh dari $D$ dengan menghapus beberapa elemen (mungkin tidak ada atau semuanya) tanpa mengubah urutan elemen-elemen yang tersisa.
Masukan
Masukan diberikan dalam format berikut:
T N A_1 A_2 ... A_N :
- Semua nilai masukan adalah bilangan bulat.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Dijamin bahwa jumlah $N^2$ di seluruh kasus uji tidak melebihi $5000^2$.
Keluaran
Untuk setiap kasus uji, keluarkan satu bilangan bulat — jumlah skor dari semua upabarisan tak kosong dari $A$, modulo $998\,244\,353$.
Contoh
Contoh Masukan 1
3 1 5 3 1 1 3 4 2 2 2 2
Contoh Keluaran 1
5 16 47
Catatan
Kasus uji 1: Satu-satunya upabarisan tak kosong adalah $[5]$, dengan skor $5$. Oleh karena itu, jawabannya adalah $5$.
Kasus uji 2: Upabarisan-upabarisan tak kosong dari $[1, 1, 3]$ adalah:
- dua upabarisan yang sama dengan $[1]$, masing-masing dengan skor $1$,
- $[3]$, dengan skor $3$,
- $[1, 1]$, dengan skor $2$,
- dua upabarisan yang sama dengan $[1, 3]$, masing-masing dengan skor $3$,
- $[1, 1, 3]$, dengan skor $3$.
Jadi, jumlah totalnya adalah $16$.