solution

考虑求答案的补集。也就是计算有多少个序列不是反复横跳的。

这样的序列肯定是单调不降序列或者是单调不升序列。

又因为所有数字不超过k。

以单调不降序列为例（单调不升序列个数与其相等）。我们枚举最后一个数字的大小。然后对这个序列做一下差分，也就是令。这样就转化成了有多少个满足条件的序列，满足什么条件呢？只要满足。这是经典的组合问题，相当于把x个物品分为b份，每份可以为空，用隔板法可以看出答案就是

所以这种序列的个数就是

因为题目要求，所以只要将上面的变为所给的k-1即可。

因为有种序列是既单调不升又单调不降的，所以要减去k。

综上，答案就是

将那个组合数拆开，发现复杂度是可以接受的。

code

/*
* @Author: wxyww
* @Date:   2020-04-17 20:59:52
* @Last Modified time: 2020-04-17 22:01:07
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
ll qm(ll x,ll y) {
    ll ret = 1;
    for(;y;y >>= 1,x = x * x % mod) {
        if(y & 1) ret = ret * x % mod;
    }
    return ret;
}
int main() {
    int T = read();
    while(T--) {
        ll n = read(),K = read();

        ll ans = (qm(K,n) + K) % mod,now = 1;

        --K;

        for(ll i = n + 1;i <= n + K;++i)
            now = now * i % mod;

        ll tmp = 1;
        for(int i = 1;i <= K;++i) tmp = tmp * i % mod;

        now = now * qm(tmp,mod - 2) % mod;

        now = (now + now) % mod;
        cout<<(ans - now + mod) % mod<<endl;

    }

    return 0;
}