P7950 [✗✓OI R1] Water Behind

This problem has no background, because I am a saint and also the right seat of god.

Define a process of merging stones as follows: there is a row of $n$ piles of stones, and the $i$-th pile has $a_i(a_i\ge1)$ stones. Each time, you may choose two adjacent piles to merge. Suppose their sizes are $x,y$, then you will get one pile of $(x+y)$ stones, and you need to pay a cost of $xy$. In the end, all piles must be merged into one pile. Let $f(a_1,\ldots,a_n)$ be the minimum cost to merge these piles of stones. Given the total number of stones $S$, compute $$ \sum_{\sum a_i=S}f(a_1,\ldots,a_n) $$ and output the answer modulo $998244353$.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain two integers $n,S$.

Output $T$ lines, each containing one integer, the answer modulo $998244353$.

**[Sample Explanation]** Explanation for the first test case in the sample: The partitions are $(1,5),(2,4),(3,3),(4,2),(5,1)$, for a total of $5$ cases. The answer is $1\times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 35$. **[Constraints]** | Test Point ID | $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$ | For $100\%$ of the testdata, $1\le T\le5$, $1\le n\le10^6$, $1\le S\le10^9$.  Translated by ChatGPT 5