Một dãy số nguyên $V_1, V_2, \dots, V_N$ được gọi là siêu giảm nếu $V_N \ge 0$, và $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ với mọi $1 \le i < N$.
Cho hai số nguyên dương $N$ và $M$, hãy tìm số cặp dãy số nguyên $A$ và $B$ có độ dài $N$ sao cho $1 \le A_i, B_i \le M$ với mọi $1 \le i \le N$, và với mọi dãy siêu giảm $V$ có độ dài $N$,
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Vì số lượng cặp như vậy có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
T N M :
- Tất cả các giá trị đầu vào đều là số nguyên.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Dữ liệu đảm bảo tổng của $N$ trên tất cả các bộ test không vượt quá $5000$.
- Dữ liệu đảm bảo tổng của $M$ trên tất cả các bộ test không vượt quá $5000$.
Kết quả
Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng cặp dãy $(A, B)$ thỏa mãn điều kiện, theo modulo $998\,244\,353$.
Ví dụ
Ví dụ đầu vào 1
4 1 1 2 2 2 1 34 43
Ví dụ đầu ra 1
1 10 1 711021868
Ghi chú
Bộ test 1: Cặp dãy duy nhất có thể là $([1], [1])$, và nó hợp lệ.
Bộ test 2: Dưới đây là các cặp dãy hợp lệ:
- Với $B = [1, 1]$, mọi cách chọn $A$ đều hợp lệ. Có $4$ cách chọn có thể.
- Với $B = [1, 2]$, các cách chọn $A$ hợp lệ là $[1, 2], [2, 1], [2, 2]$.
- Với $B = [2, 1]$, các cách chọn $A$ hợp lệ là $[2, 1], [2, 2]$.
- Với $B = [2, 2]$, cách chọn $A$ hợp lệ duy nhất là $[2, 2]$.
Vì vậy, số lượng cặp dãy hợp lệ bằng $4 + 3 + 2 + 1 = 10$.