Gọi $B$ là một mảng có độ dài $M$ gồm các số nguyên dương.
Trong một thao tác, bạn có thể chọn một dãy con khác rỗng$^\dagger$ các chỉ số $1 \le i_1 < i_2 < \dots < i_k \le M$ sao cho các giá trị $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ đôi một phân biệt, rồi giảm mỗi giá trị được chọn đi $1$.
Định nghĩa điểm số của $B$, ký hiệu là $\text{score}(B)$, là số thao tác ít nhất cần thiết để biến mọi phần tử của $B$ thành $0$.
Bạn được cho một mảng $A$ có độ dài $N$.
Hãy tìm tổng điểm số trên tất cả các dãy con khác rỗng của $A$.
Vì giá trị này có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.
$^\dagger$ Một dãy $C$ được gọi là một dãy con của dãy $D$ nếu có thể thu được nó từ $D$ bằng cách xóa một số phần tử (có thể không xóa phần tử nào hoặc xóa tất cả) mà không làm thay đổi thứ tự của các phần tử còn lại.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
T N A_1 A_2 ... A_N :
- Tất cả các giá trị đầu vào đều là số nguyên.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Dữ liệu đảm bảo tổng của $N^2$ trên tất cả các bộ test không vượt quá $5000^2$.
Kết quả
Với mỗi bộ test, in ra một số nguyên duy nhất — tổng điểm số trên tất cả các dãy con khác rỗng của $A$, theo modulo $998\,244\,353$.
Ví dụ
Ví dụ đầu vào 1
3 1 5 3 1 1 3 4 2 2 2 2
Ví dụ đầu ra 1
5 16 47
Ghi chú
Bộ test 1: Dãy con khác rỗng duy nhất là $[5]$, có điểm số là $5$. Do đó, đáp án là $5$.
Bộ test 2: Các dãy con khác rỗng của $[1, 1, 3]$ là:
- hai dãy con bằng $[1]$, mỗi dãy có điểm số là $1$,
- $[3]$, có điểm số là $3$,
- $[1, 1]$, có điểm số là $2$,
- hai dãy con bằng $[1, 3]$, mỗi dãy có điểm số là $3$,
- $[1, 1, 3]$, có điểm số là $3$.
Vì vậy, tổng cộng là $16$.