Una secuencia de enteros $V_1, V_2, \dots, V_N$ se llama superdecreciente si $V_N \ge 0$, y $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ para todo $1 \le i < N$.
Dados los enteros positivos $N$ y $M$, halla el número de pares de secuencias de enteros $A$ y $B$ de longitud $N$ tales que $1 \le A_i, B_i \le M$ para todo $1 \le i \le N$, y para todas las secuencias superdecrecientes $V$ de longitud $N$,
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Como el número de tales pares puede ser muy grande, imprime la respuesta módulo $998\,244\,353$.
Entrada
La entrada se proporciona en el siguiente formato:
T N M :
- Todos los valores de entrada son enteros.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Se garantiza que la suma de $N$ en todos los casos de prueba no supera $5000$.
- Se garantiza que la suma de $M$ en todos los casos de prueba no supera $5000$.
Salida
Para cada caso de prueba, imprime un único entero: el número de pares de secuencias $(A, B)$ que cumplen las condiciones, módulo $998\,244\,353$.
Ejemplos
Entrada de ejemplo 1
4 1 1 2 2 2 1 34 43
Salida de ejemplo 1
1 10 1 711021868
Nota
Caso de prueba 1: El único par de secuencias posible es $([1], [1])$, y es válido.
Caso de prueba 2: Los siguientes son pares de secuencias válidos:
- Para $B = [1, 1]$, cualquier elección de $A$ es válida. Hay $4$ elecciones posibles.
- Para $B = [1, 2]$, las elecciones válidas de $A$ son $[1, 2], [2, 1], [2, 2]$.
- Para $B = [2, 1]$, las elecciones válidas de $A$ son $[2, 1], [2, 2]$.
- Para $B = [2, 2]$, la única elección válida de $A$ es $[2, 2]$.
Por lo tanto, el número de pares de secuencias válidos es igual a $4 + 3 + 2 + 1 = 10$.