#P18317. Easy Counting Problem

Easy Counting Problem

Easy Counting Problem

给定数组 AA,你可以执行任意次以下操作,也可以一次不执行:

  • 选择一个满足 1≤i≤∣A∣1\le i\le |A| 且 Ai=iA_i=i 的下标 ii,删除数组的第 ii 个元素。
  • 删除后,数组变为 A[1,i−1]+A[i+1,∣A∣]A[1,i-1]+A[i+1,|A|]。这里 A[L,R]A[L,R] 表示由 AL,AL+1,…,ARA_L,A_{L+1},\ldots,A_R 组成的子数组,++ 表示连接。空的部分直接忽略。

下标从1开始。每次操作判断的是当前数组的下标;删除后,后面的元素向前移动。

令 f(A)f(A) 表示最优地执行这些操作后,数组能够达到的最小长度。

给定整数 N,MN,M,考虑全部长度为 NN、满足 1≤Ai≤M1\le A_i\le M 的数组,共有 MNM^N 个。求所有这些数组的 f(A)f(A) 之和,对 998244353998244353 取模。

输入格式

第一行包含整数 TT,表示测试用例数。

接下来 TT 行,每行包含两个整数 N,MN,M,描述一组测试用例。

输出格式

对于每组测试用例,输出一行,包含所有符合条件的数组的 f(A)f(A) 之和对 998244353998244353 取模后的结果。

数据范围

  • 1≤T≤101\le T\le10;
  • 1≤N,M<9982443531\le N,M<998244353;
  • ∣N−M∣≤2000|N-M|\le2000。

样例

输入

9
2 2
2 1
3 1
3 2
3 3
3 5
6 3
23 10
900000000 900000000

输出

3
0
0
9
44
284
2534
243195864
193285282

说明

第一组测试中共有 22=42^2=4 个数组:

  • [1,1][1,1]:先删除第1个元素,再删除当前第1个元素,故 f=0f=0。
  • [1,2][1,2]:先删除第2个元素,再删除第1个元素,故 f=0f=0。
  • [2,1][2,1]:无法执行任何操作,故 f=2f=2。
  • [2,2][2,2]:删除第2个元素后剩下 [2][2],故 f=1f=1。

因此答案为 0+0+2+1=30+0+2+1=3。