יהי $B$ מערך באורך $M$ המורכב ממספרים שלמים חיוביים.
בפעולה אחת, תוכלו לבחור תת-סדרה לא ריקה$^\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$.
נתון מערך $A$ באורך $N$.
מצאו את סכום הניקודים על פני כל תת-הסדרות הלא ריקות של $A$.
מכיוון שהערך עשוי להיות גדול, הדפיסו אותו מודולו $998\,244\,353$.
$^\dagger$ סדרה $C$ נקראת תת-סדרה של סדרה $D$ אם ניתן לקבל אותה מ-$D$ על ידי מחיקת מספר איברים, ייתכן שאף אחד או כולם, מבלי לשנות את סדר האיברים הנותרים.
קלט
הקלט ניתן בפורמט הבא:
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$.
פלט
עבור כל מקרה בדיקה, הדפיסו מספר שלם יחיד — סכום הניקודים על פני כל תת-הסדרות הלא ריקות של $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]$, כל אחת עם ניקוד $1$,
- $[3]$, עם ניקוד $3$,
- $[1, 1]$, עם ניקוד $2$,
- שתי תת-סדרות השוות ל-$[1, 3]$, כל אחת עם ניקוד $3$,
- $[1, 1, 3]$, עם ניקוד $3$.
לכן, הסכום הכולל הוא $16$.