P9554 「CROI · R1」Raccoon’s Creek Stones

>Looking back to the past, the sky was clear, the sun was warm, and the breeze was gentle.\ Creek stones, with different depths and heights, were scattered in the crystal-clear Mengfeng Creek like jade.\ The endless fun memories of raccoons doing parkour on the water also began here...

As the sun rises and the moon sets, spring goes and autumn comes, the heights of the Mengfeng creek stones change in countless ways. The thoughtful little raccoon CleverRaccoon wants to find out how many different height sequences these creek stones can form. Now there are some non-negative integer sequences $a$ of length $n$. When $n>1$, $a_1,a_n$ take values in $0\sim m$, and the other elements $a_i$ take values in $0\sim m-1$, where $2\leq i \leq n-1$. When $n=1$, $a_1$ takes values in $0\sim m+1$. **Definition**: Sequences $a,b$ are considered the same if and only if either $\forall i\in\{1,2,\dots ,n\},a_i=b_i$ or $\forall i\in\{1,2,\dots ,n\},a_i=b_{n-i+1}$. Given $n,m$, find the maximum number of **different** sequences. Output the answer modulo $998244353$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain two positive integers $n,m$ separated by spaces, with meanings as described above.

Output $T$ lines. For each test case, output one positive integer, the answer modulo $998244353$.

#### Explanation #1 When $n=1,m=3$, $a_i\in\{0,1,2,3,4\}$, so there are $5$ different height sequences in total. When $n=2,m=2$, there are $6$ different height sequences in total, listed as follows: |Index|$a_1=$|$a_2=$| |:-:|:-:|:-:| |$1$|$0$|$0$| |$2$|$0$|$1$| |$3$|$0$|$2$| |$4$|$1$|$1$| |$5$|$1$|$2$| |$6$|$2$|$2$| #### Constraints **This problem uses bundled Subtasks.** |Subtask|$n\leq$|$m\leq$|$T\leq$|Special Property|Score| |:-:|:-:|:-:|:-:|:-:|:-:| |$0$|$10$|$10$|$10$|None|$10$| |$1$|$10^3$|$1$|$10^3$|$m=1$|$5$| |$2$|$10^3$|$3$|$10$|$m=3$|$10$| |$3$|$10^3$|$10^3$|$1$|None|$15$| |$4$|$10^6$|$10^3$|$100$|None|$10$| |$5$|$10^6$|$10^6$|$10^6$|None|$20$| |$6$|$10^9$|$10^9$|$10^6$|$n$ is odd|$10$| |$7$|$10^9$|$10^9$|$10^6$|$n$ is even|$10$| |$8$|$10^{18}$|$10^9$|$10^6$|None|$10$| For $100\%$ of the testdata, it is guaranteed that $1\leq n\leq10^{18},1\leq m\leq10^9,1\leq T\leq10^6$. Translated by ChatGPT 5