정수 수열 $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$을 만족할 때, 이 수열을 초감소(super decreasing) 수열이라고 부릅니다.
양의 정수 $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$입니다.