题目描述

你有 $n!$ 个长度为 $n$ 的排列，它们已经按照字典序排好了顺序。

请你在字典序顺序中前 $S$ 个排列里寻找一个排列 $p$，使得 $\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_j$ 最大。你只需要输出这个最大值即可。

由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

第一行，一个整数 $T$。

接下来 $T$ 行，每行两个整数 $n,S$。

输出格式

共 $T$ 行，每行一个整数，表示最大的 $\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_j$，对 $998244353$ 取模。

1
4 5

23

提示

【样例 #1 解释】

长度为 $4$ 的排列的前五个分别为：

$1,2,3,4 \to 1+(1+2)+(1+2+3)+(1+2+3+4)=20$

$1,2,4,3 \to 1+(1+2)+(1+2+4)+(1+2+4+3)=21$

$1,3,2,4 \to 1+(1+3)+(1+3+2)+(1+3+2+4)=21$

$1,3,4,2 \to 1+(1+3)+(1+3+4)+(1+3+4+2)=23$

$1,4,2,3 \to 1+(1+4)+(1+4+2)+(1+4+2+3)=23$

最大值为 $23$。

【数据范围】

$\text{Subtask}$	分值	特殊性质
$1$	$10$	$n\le8$
$2$		$T\le20,n\le16$
$3$	$25$	$T\le10^4$
$4$	$5$	$S=n!$
$5$	$50$	无特殊性质

对于 $100\%$ 的数据，$1 \le T \le 10^5, 1 \le n \le 10^9, 1 \le S \le \min(n!,10^{18})$。