「CROI · R1」浣熊的溪石

题目背景

>回首往昔,碧空如洗,日暖风恬。\ 溪石深浅有致地错落在明澈似玉的梦枫溪里。\ 浣熊们水上跑酷的无限趣忆亦于此伊始……

题目描述

日升月落,春去秋来,梦枫溪石的高度千变万化。 爱思考的小浣熊 CleverRaccoon 想探寻这些溪石究竟能构成多少种不同的高度序列。 现有若干个长度为 $n$ 的非负整数列 $a$。 当 $n>1$ 时,$a_1,a_n$ 的取值为 $0\sim m$,其它数 $a_i$ 的取值为 $0\sim m-1$,其中 $2\leq i \leq n-1$。 当 $n=1$ 时,$a_1$ 的取值为 $0\sim m+1$。 **定义**:当且仅当 $\forall i\in\{1,2,\dots ,n\},a_i=b_i$ 或 $\forall i\in\{1,2,\dots ,n\},a_i=b_{n-i+1}$ 时,数列 $a,b$ 相同。 现给定 $n,m$,请求出最多有多少个**不同**的数列,答案对 $998244353$ 取模。

输入输出格式

输入格式


**本题包含多组测试数据。** 第一行,输入一个正整数 $T$,表示数据组数。 接下来 $T$ 行,每行输入以空格间隔的 $2$ 个正整数 $n,m$,意义见题目描述。

输出格式


共 $T$ 行,对于每组数据,一行输出一个正整数,表示答案对 $998244353$ 取模的结果。

输入输出样例

输入样例 #1

3
1 3
2 2
6 3

输出样例 #1

5
6
666

说明

#### 解释 #1 当 $n=1,m=3$ 时,$a_i\in\{0,1,2,3,4\}$,共有 $5$ 种不同的高度序列。 当 $n=2,m=2$ 时,共有 $6$ 种不同的高度序列,详情如下: |序号|$a_1=$|$a_2=$| |:-:|:-:|:-:| |$1$|$0$|$0$| |$2$|$0$|$1$| |$3$|$0$|$2$| |$4$|$1$|$1$| |$5$|$1$|$2$| |$6$|$2$|$2$| #### 数据范围 **本题采用 Subtask 捆绑测试。** |Subtask|$n\leq$|$m\leq$|$T\leq$|特殊性质|Score| |:-:|:-:|:-:|:-:|:-:|:-:| |$0$|$10$|$10$|$10$|无特殊性质|$10$| |$1$|$10^3$|$1$|$10^3$|$m=1$|$5$| |$2$|$10^3$|$3$|$10$|$m=3$|$10$| |$3$|$10^3$|$10^3$|$1$|无特殊性质|$15$| |$4$|$10^6$|$10^3$|$100$|无特殊性质|$10$| |$5$|$10^6$|$10^6$|$10^6$|无特殊性质|$20$| |$6$|$10^9$|$10^9$|$10^6$| $n$ 为奇数|$10$| |$7$|$10^9$|$10^9$|$10^6$| $n$ 为偶数|$10$| |$8$|$10^{18}$|$10^9$|$10^6$|无特殊性质|$10$| 对于 $100\%$ 的数据,保证 $1\leq n\leq10^{18},1\leq m\leq10^9,1\leq T\leq10^6$。