一個整數序列 $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$。