P11748 「TPOI-1B」ASPAP

You have $n!$ permutations of length $n$ sorted in lexicographical order. Among the first $S$ permutations in this order, find a permutation $p$ that maximizes $\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_j$. Output this maximum value modulo $998244353$.

The first line contains an integer $T$. Each of the next $T$ lines contains two integers $n$ and $S$.

For each query, output one integer representing the maximum value modulo $998244353$.

**Explanation for Sample #1** The first five permutations of length $4$ are: - $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$ The maximum value is $23$. **Constraints** This problem uses bundled tests. You must pass all test cases in a subtask to receive points. | Subtask | Points | Special Constraints | |:-:|:-:|:-:| | 1 | 10 | $n \le 8$ | | 2 | 10 | $T \le 20$, $n \le 16$ | | 3 | 25 | $T \le 10^4$ | | 4 | 5 | $S = n!$ | | 5 | 50 | No special constraints | For $100\%$ data: $1 \le T \le 10^5$, $1 \le n \le 10^9$, $1 \le S \le \min(n!,\ 10^{18})$. Translated by DeepSeek R1