Sequence Domination
一个长度为 N 的整数序列 V 称为超递减序列,如果 VN≥0,且对每个 1≤i<N 都有
Vi≥Vi+1+Vi+2+⋯+VN.
给定正整数 N,M,求有多少对长度为 N 的整数序列 (A,B) 满足:
- 对所有 i,1≤Ai,Bi≤M;
- 对每一个长度为 N 的超递减整数序列 V,均有
i=1∑NAiVi≥i=1∑NBiVi.
答案对 998244353 取模。
输入格式
第一行一个整数 T。接下来 T 行,每行两个整数 N,M,表示一组数据。
输出格式
每组数据输出一行一个整数,表示合法序列对的数量对 998244353 取模后的结果。
数据范围
1≤T≤100,1≤N,M≤5000。所有测试用例的 N 之和不超过 5000,M 之和也不超过 5000。
样例 1
输入
4
1 1
2 2
2 1
34 43
输出
1
10
1
711021868