#P18229. Safety First

Safety First

Safety First

一架梯子由 nn 段组成,每段长度都是正整数,且从左到右非递增。记各段长度为 d1,d2,…,dnd_1,d_2,\ldots,d_n,则

d1≥d2≥⋯≥dn≥1.d_1\ge d_2\ge\cdots\ge d_n\ge1.

梯子竖立后的高度,是最高点和最低点的高度差。下图表示梯子的分段和高度 mm:

原题梯子分段与高度示意

小 Q 需要一架高度恰好为 mm 的稳定梯子。稳定要求:

  • 第一段的下端接触地面;
  • 对每个 i=1,2,…,n−1i=1,2,\ldots,n-1,第 ii 段的上端必须锁定在第 i+1i+1 段的上端或下端。

下图左侧的连接不稳定;中间和右侧分别表示锁定在下一段上端、下端的两种稳定连接:

原题稳定和不稳定的连接方式

求长度为 nn 段、高度恰好为 mm 的不同稳定梯子数量,对 998244353998244353 取模。

如果某一段的长度不同,或者某对相邻段的锁定方式不同,就视为两架不同的梯子。即使各段长度完全相同,不同锁定方式也可能对应不同梯子。

输入格式

第一行包含整数 TT,表示询问数量。

接下来 TT 行,每行包含两个整数 n,mn,m。

输出格式

对每个询问输出一行,包含一个整数,表示答案对 998244353998244353 取模的结果。

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 1≤n,m≤20001\le n,m\le2000。

本题没有额外的询问总规模限制。

样例 1

3
1 3
2 3
3 3
1
4
10

样例 2

1
2000 2000
204576309

样例说明

在样例 1 中:

  • (n,m)=(1,3)(n,m)=(1,3):唯一的梯子只有一段,长度为 33。
  • (n,m)=(2,3)(n,m)=(2,3):段长分别可以是 [2,1][2,1]、[3,1][3,1]、[3,2][3,2]、[3,3][3,3]。第一种把第一段上端接到第二段下端,后三种接到第二段上端。
  • (n,m)=(3,3)(n,m)=(3,3):十种方案的段长为 [1,1,1][1,1,1]、[2,1,1][2,1,1]、[2,1,1][2,1,1]、[2,2,1][2,2,1]、[3,1,1][3,1,1]、[3,2,1][3,2,1]、[3,2,2][3,2,2]、[3,3,1][3,3,1]、[3,3,2][3,3,2]、[3,3,3][3,3,3]。其中两份 [2,1,1][2,1,1] 的锁定方式不同:分别让第二段或第三段向总高度贡献其长度。