P7950 [✗✓OI R1] 后方之水
题目背景
这个题目没有背景，因为我是圣人的同时还是神之右席。
题目描述
定义一次石子合并的过程如下：有一排 $n$ 堆石子，每一堆有 $a_i(a_i\ge1)$ 个。每次你可以选择相邻的两堆石子合并，设个数分别为 $x,y$，则你会得到一堆 $(x+y)$ 个石子，同时你要付出 $xy$ 的代价。最后要把所有石子合并成一堆。记 $f(a_1,\ldots,a_n)$ 为合并这些石子的最小代价。
给出石子总数 $S$，求
$$ \sum_{\sum a_i=S}f(a_1,\ldots,a_n) $$
答案对 $998244353$ 取模。
输入格式
**本题有多组测试数据。**
第一行一个整数 $T$，表示测试数据的数量。
接下来 $T$ 行，每行两个整数，分别为 $n,S$。
输出格式
$T$ 行，每行一个整数，表示答案对 $998244353$ 取模的结果。
说明/提示
**【样例解释】**
对第一个样例的第一组数据解释：
划分有 $(1,5),(2,4),(3,3),(4,2),(5,1)$，共 $5$ 种。
答案为 $1\times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 35$。
**【数据范围】**
| 测试点编号 | $n$ | $S$
| :--------: | :-------: | :-------: |
| 1,2 | $\le15$ | $\le15$ |
| 3,4 | $\le40$ | $\le40$ |
| 5,6,7 | $\le70$ | $\le70$ |
| 8,9 | $\le200$ | $\le200$ |
| 10,11 | $\le2000$ | $\le2000$ |
| 12,13,14 | $\le10^6$ | $\le10^6$ |
| 15 | $=2$ | $\le10^9$ |
| 16,17,18 | $\le2000$ | $\le10^9$ |
| 19~25 | $\le10^6$ | $\le10^9$ |
对于 $100\%$ 的数据，有 $1\le T\le5$，$1\le n\le10^6$，$1\le S\le10^9$。
