Zeryq

题目描述

小 Y 有一个 $n$ 个数的排列 $a_i$，他因为计算行列式系数时算麻了，所以他想让排列中不存在由某个数组成的逆序对，记这个数为 $x$，即排列中不能存在逆序对 $(x,y)$ 或 $(z,x)$ （其中 $x,y,z$ 均为数值，而非下标，且 $y<x<z$），他可以进行如下操作若干次使排列合法。

对于一次操作，小 Y 可以选择一对 $l,r(1\le l \le r\le n)$，把区间 $[l,r]$ 的 $a_i$ 整体平移到排列的开头或者末尾，即排列变成 $a_1...a_{l-1}a_{r+1}...a_na_l...a_r$ 或者 $a_l...a_ra_1...a_{l-1}a_{r+1}...a_n$。

定义 $f(i)$ 为使排列中不存在由 $i$ 组成的逆序对时所需的最小操作次数。

小 Y 不希望操作太多次，所以请你帮忙求 $\sum_{i=1}^n f(i)\le m$ 的排列方案数。

因为答案可能很大，所以答案需要对于 $998244353$ 取模。

输入格式

共 $T$ 组数据。

对于每组数据，输入两个整数 $n$ 和 $m$，表示排列的长度以及限制。

输出格式

输出总共 $T$ 行。

对于每组数据输出一个整数，表示答案。

输入输出样例 #1

输入 #1

5
3 2
3 6
5 4
8 8
19 23

输出 #1

3
6
25
1667
316603214

说明/提示

样例第一组，$(1,2,3),(1,3,2),(2,1,3)$ 为满足条件的排列。其中 $(1,3,2)$ 的 $f(2)=f(3)=1$ ，均可以只进行一次操作把 $[2,2]$ 平移到末尾使排列变成 $(1,2,3)$ ，此时无 $2$ 或 $3$ 构成的逆序对；$(2,1,3)$ 的 $f(2)=f(1)=1$ ，均可以只进行一次操作把 $[2,2]$ 平移到 开头使排列变为 $(1,2,3)$ ，此时无 $1$ 或 $2$ 构成的逆序对。

样例第二组，所有排列均满足 $\sum_{i=1}^3 f(i)\le 6$ ，所以答案为 $3!=6$。

样例第三组，$(2,1,3,5,4)$ 为满足条件的排列之一 ，其中 $f(1)=f(2)=f(4)=f(5)=1,f(3)=0$ ，故 $\sum_{i=1}^5 f(i)=4$ 。

【样例2】

见 sample2.in 和 sample2.out

该样例数据满足测试点编号 $18$ 对应的限制。

样例文件下载

样例文件下载

数据范围及约定

对于 $100$% 的数据： $2\le n\le 100,0 \le m\le n^2,1\le T\le 10^5$。

测试点编号 $T$	$n \leq$	$m \leq$	$T\le$
$1, 2$	$5$	$n^2$	$5$
$3$	$8$
$4$	$9$
$5$	$10$
$6$	$20$	$2$	$20$
$7$		$3$
$8$		$4$
$9$		$5$
$10,11,12$		$n^2$	$1$
$13$	$100$	$1$	$10^5$
$14 \sim 20$	$(T-10)\times 10$	$n^2$