一個整數序列 $V_1, V_2, \dots, V_N$ 被稱為超遞減的,如果 $V_N \ge 0$,且對於所有 $1 \le i < N$,均滿足 $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$。
給定正整數 $N$ 和 $M$,求滿足以下條件的長度為 $N$ 的整數序列 $A$ 和 $B$ 的配對數量:對於所有 $1 \le i \le N$,均有 $1 \le A_i, B_i \le M$,且對於所有長度為 $N$ 的超遞減序列 $V$,均滿足:
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
由於滿足條件的序列對數量可能非常大,請將答案對 $998\,244\,353$ 取模後輸出。
輸入格式
輸入按以下格式給出:
T N M :
- 所有輸入值均為整數。
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- 保證所有測試資料中 $N$ 的總和不超過 $5000$。
- 保證所有測試資料中 $M$ 的總和不超過 $5000$。
輸出格式
對於每組測試資料,輸出一個整數——表示滿足條件的序列對 $(A, B)$ 的數量對 $998\,244\,353$ 取模後的結果。
範例
範例輸入 1
4 1 1 2 2 2 1 34 43
範例輸出 1
1 10 1 711021868
說明
測試資料 1:唯一可能的序列對是 $([1], [1])$,且它是合法的。
測試資料 2:以下是合法的序列對:
- 對於 $B = [1, 1]$,任意 $A$ 的選擇都是合法的。共有 $4$ 種可能的選擇。
- 對於 $B = [1, 2]$,合法的 $A$ 選擇為 $[1, 2], [2, 1], [2, 2]$。
- 對於 $B = [2, 1]$,合法的 $A$ 選擇為 $[2, 1], [2, 2]$。
- 對於 $B = [2, 2]$,唯一合法的 $A$ 選擇為 $[2, 2]$。
因此,合法的序列對數量等於 $4 + 3 + 2 + 1 = 10$。