Целочисленная последовательность $V_1, V_2, \dots, V_N$ называется сверхубывающей, если $V_N \ge 0$ и $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ для всех $1 \le i < N$.
Даны положительные целые числа $N$ и $M$. Найдите количество пар целочисленных последовательностей $A$ и $B$ длины $N$, таких что $1 \le A_i, B_i \le M$ для всех $1 \le i \le N$, и для всех сверхубывающих последовательностей $V$ длины $N$ выполняется:
$$\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$.