// min(n, m) = 0 の場合分け漏れ #include #include #include #include using mint = atcoder::modint998244353; template using Matrix = std::array, M>; template Matrix operator*(const Matrix& A, const Matrix& B) { Matrix C{}; for (size_t i = 0; i < N; ++i) for (size_t j = 0; j < M; ++j) for (size_t k = 0; k < K; ++k) { C[i][k] += A[i][j] * B[j][k]; } return C; } template std::array operator*(const Matrix& A, const std::array& x) { std::array y{}; for (size_t i = 0; i < N; ++i) for (size_t j = 0; j < M; ++j) { y[i] += A[i][j] * x[j]; } return y; } template Matrix pow(Matrix A, unsigned long long k) { Matrix B{}; for (size_t i = 0; i < N; ++i) B[i][i] = 1; for (; k; k >>= 1) { if (k & 1) B = B * A; A = A * A; } return B; } constexpr size_t MAX_N = 10000000; std::array g; void init_g() { g.fill(0); g[0] = 1; for (size_t i = 1; i <= MAX_N; ++i) { g[i] += g[i - 1] * (2 * i); if (i >= 2) { g[i] += g[i - 2] * (i - 1); } } } mint solve(uint32_t n, uint64_t m) { if (n > m) { uint64_t tmp = n; n = m, m = tmp; } Matrix A{ 0, 1, n, 2 * n + 1 }; mint fn1 = g[n - 1], fn = g[n]; auto [fm1, fm] = pow(A, m - n) * std::array { fn1, fn }; return fm1 * fn1 * n + fm * fn; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); init_g(); uint32_t t; std::cin >> t; for (uint32_t case_id = 0; case_id < t; ++case_id) { uint32_t n; uint64_t m; std::cin >> n >> m; std::cout << solve(n, m).val() << '\n'; } }