MOD = 998244353i64 read_line.to_i.times do puts solve end def solve n, m = read_line.split.map(&.to_i) sel02 = n == 2 ? 0i64 : n.to_i64 * (n - 3) // 2 sel12 = n == 2 ? 0i64 : (sel02 - (n - 3) + MOD) % MOD sel22 = n == 2 ? 0i64 : (sel02 - (n - 3) * 2 + 1 + MOD) % MOD dp = Array.new(m + 1) { Array.new(3, 0i64) } dp[0][0] = 1 1.upto(m) do |i| dp[i][0] = dp[i - 1].sum % MOD dp[i][1] = dp[i - 1][0] * n dp[i][1] += dp[i - 1][1] * (n - 1) dp[i][1] += dp[i - 1][2] * (n - 2) dp[i][1] %= MOD dp[i][2] = dp[i - 1][0] * sel02 dp[i][2] += dp[i - 1][1] * sel12 dp[i][2] += dp[i - 1][2] * sel22 dp[i][2] %= MOD end return dp[-1].sum % MOD end