There is an empty grid (all cells are colored white) of N rows and M columns.

Chef can fill each cell with either RED or GREEN color.  
Chef defines a *valid* path as a path of cells starting from (1,1) and ending at (N,M), where, Chef moves either right or down by 1 cell each time.

For a particular grid, Chef defines the *score* of the grid as the number of *valid* paths containing equal number of RED and GREEN cells.

Find the sum of *scores* of all possible colored grids containing N rows and M columns.  
Since the answer can be large, output it modulo 998244353.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two integers N and M - denoting the dimensions of the grid.

------ Output Format ------ 

For each test case, output the sum of *scores* of all possible colored grids containing N rows and M columns, modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N, M ≤ 1000$

----- Sample Input 1 ------ 
3
1 1
1 2
2 3

----- Sample Output 1 ------ 
0
2
72

----- explanation 1 ------ 
Test case $1$: There are $2$ possible coloured grids of size $1 \times 1$. In the first grid, the one and only cell is colored RED. In the second grid, the one and only cell is colored GREEN. Neither of the grids have a *valid* path with equal number of red and green cells. Thus, score of each grid is $0$.

Test case $2$: There are $4$ possible coloured grids of the given dimension:

For grids $1$ and $4$, the scores are $0$ as there are no valid paths with equal red and green cells. Grids $2$ and $3$ have score $1$ each. The valid path with equal red and green cells is $(1,1) \rightarrow (1,2)$ in both the grids.

Thus, the sum of scores of all possible coloured grids is $2$.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
md = 998244353
fact = [1]
prod = 1
for i in range(1, 2000):
	prod = prod * i % md
	fact.append(prod)

def binom(a, b):
	rv = 1
	while b != 0:
		rv = rv * pow(b, -1, md) % md
		b -= 1
		rv = rv * (a - b) % md
	return rv
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	if (m + n) % 2 == 0:
		print(0)
		continue
	ans = binom(m + n - 1, (m + n - 1) // 2)
	ans = ans * binom(m + n - 2, m - 1) % md
	ans = ans * pow(2, (m - 1) * (n - 1), md) % md
	print(ans)


import math
t = int(input())
for _ in range(t):
	(m, n) = list(map(int, input().split()))
	mod = 998244353
	if (m + n - 1) % 2:
		print(0)
	else:
		print(2 ** (n * m - (n + m - 1)) * math.comb(m + n - 1, (m + n - 1) // 2) * math.comb(m + n - 2, n - 1) % mod)


from math import comb

def colorgrid(N, M):
	if (N + M - 1) % 2 != 0:
		return 0
	else:
		return 2 ** (N * M - (N + M - 1)) * comb(N + M - 1, (N + M - 1) // 2) * comb(N + M - 2, N - 1)
t = int(input())
while t:
	(N, M) = list(map(int, input().split(' ')))
	res = colorgrid(N, M) % 998244353
	print(res)
	t = t - 1


from math import comb
mod = 998244353
test = int(input())
while test:
	(n, m) = map(int, input().split())
	if (m + n - 1) % 2:
		print(0)
	else:
		print(2 ** (n * m - (n + m - 1)) * comb(m + n - 1, (m + n - 1) // 2) * comb(m + n - 2, n - 1) % mod)
	test -= 1


def fact(n):
	if n == 0:
		return 1
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	if (N + M - 1) % 2:
		print(0)
	else:
		paths = fact(N + M - 2) // (fact(N - 1) * fact(M - 1))
		total = N + M - 1
		ways = fact(total) // (fact(total // 2) * fact(total - total // 2))
		ans = paths * ways * 2 ** (N * M - total) % 998244353
		print(ans)


mod = 998244353
n = 2005
c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	c[i][0] = 1
for i in range(1, n):
	for j in range(1, i + 1):
		c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	len = n + m - 1
	ans = c[n + m - 2][m - 1] * c[len][len // 2] * pow(2, n * m - len, mod)
	if len % 2 == 1:
		ans = 0
	print(ans % mod)


def arrangement(n, m):
	a = min(m, n)
	b = max(m, n)
	t = m + n
	num = 1
	for i in range(b + 1, t + 1):
		num *= i
	den = 1
	for i in range(2, a + 1):
		den *= i
	return num // den
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if (n + m) % 2 == 0:
		print(0)
	else:
		w = arrangement(n - 1, m - 1)
		t = 2 ** (m * n - (m + n - 1))
		b = arrangement((m + n - 1) // 2, (m + n - 1) // 2)
		total = w * t * b
		print(total % 998244353)


N = 2050
M = 998244353
f = [[0] * N for i in range(N)]
for i in range(1, N):
	f[i][i] = 1
	f[i][0] = 1
for i in range(1, N):
	for j in range(1, i):
		f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % M
g = [1] * (N * N)
for i in range(1, N * N):
	g[i] = 2 * g[i - 1] % M
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if (n + m) % 2 == 0:
		print(0)
		continue
	k = n + m - 1
	ans = f[n + m - 2][n - 1]
	ans = ans * f[k][k // 2] % M
	ans = ans * g[n * m - k] % M
	print(ans)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	modulo = 998244353
	facts = [1]
	for i in range(1, 2001):
		facts.append(facts[-1] * i)
	steps = n + m - 1
	if steps % 2 != 0:
		print(0)
	else:
		ans = facts[steps] // facts[steps // 2] ** 2 * 2 ** (n * m - steps) * (facts[n + m - 2] // (facts[n - 1] * facts[m - 1]))
		print(ans % modulo)


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
mod = 998244353
ls = [[0 for i in range(1001)] for j in range(1001)]
for i in range(1001):
	ls[i][0] = 1
	ls[0][i] = 1
for i in range(1, 1001):
	for j in range(1, 1001):
		ls[i][j] = ls[i - 1][j] + ls[i][j - 1]
		ls[i][j] %= mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if (n + m) % 2 == 0:
		print(0)
	else:
		ans = ls[n - 1][m - 1] * 2 ** (n * m - n - m + 1)
		ans %= mod
		ans *= ncr(n + m - 1, (n + m - 1) // 2, mod)
		print(ans % mod)


import math
t = int(input())
K = 998244353
for i in range(t):
	(N, M) = map(int, input().split())
	if (N + M) % 2 == 0:
		print(0)
	else:
		a = math.comb(M + N - 2, M - 1)
		b = math.comb(M + N - 1, (M + N - 1) // 2)
		c = 2 ** (M * N - (M + N - 1))
		ans = a * b * c
		print(ans % K)


import math

def back(r1, c1):
	a = {c1 - 1: 1}
	b = {}
	for i in range(r1 - 1, -1, -1):
		for j in range(c1 - 1, -1, -1):
			if i == r1 - 1 and j == c1 - 1:
				continue
			a[j] = a.get(j + 1, 0) + b.get(j, 0)
		(a, b) = ({}, a)
	return b[0]
for _ in range(int(input())):
	(row, col) = list(map(int, input().split()))
	if (row + col - 1) % 2 or row == col == 1:
		print(0)
	else:
		ans = math.comb(row + col - 2, row - 1) * pow(2, row * col - (row + col - 1), 998244353) * math.comb(row + col - 1, (row + col - 1) // 2)
		print(ans % 998244353)


facts = []
modinv = []
modn = 998244353

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y % 2 == 1:
			res = res * x % p
		y = int(y / 2)
		x = x * x % p
	return res

def modInverse(n, p):
	return power(n, p - 2, modn)

def nCrModPFermat(n, r, p):
	if n < r:
		return 0
	elif r == 0:
		return 1
	else:
		return facts[n] * modinv[r] % modn * modinv[n - r] % modn
facts.append(1)
for i in range(1, 2002):
	k = facts[i - 1] * i
	facts.append(k % modn)
modinv.append(1)
for i in range(1, 2000):
	modinv.append(modInverse(facts[i], modn))
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	L = N + M - 1
	if L % 2 == 1:
		print(0)
	else:
		answ = nCrModPFermat(N + M - 2, M - 1, modn)
		answ = answ * nCrModPFermat(L, int(L / 2), modn) % modn
		answ = answ * power(2, N * M - L, modn) % modn
		print(answ)


import math
BASE = 998244353
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	steps = n + m - 2
	if steps % 2 == 0:
		print(0)
	else:
		num_of_paths = math.comb(steps, n - 1) % BASE
		valid_paths = math.comb(steps + 1, (steps + 1) // 2) % BASE
		rest_grid_coloring = pow(2, n * m - steps - 1, BASE)
		print(num_of_paths * valid_paths * rest_grid_coloring % BASE)


import math
mod = 998244353
for t in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	if (n + m - 1) % 2 == 0:
		ans = math.comb(n + m - 2, n - 1) % mod * (math.comb(n + m - 1, (n + m - 1) // 2) % mod) * pow(2, n * m - (n + m - 1), mod) % mod
		print(ans)
	else:
		print(0)


from math import comb
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n % 2 == 0 and m % 2 == 0:
		print(0)
	elif n % 2 == 1 and m % 2 == 1:
		print(0)
	else:
		path = comb(m + n - 2, n - 1) % 998244353
		color = comb(m + n - 1, (m + n - 1) // 2) % 998244353
		nr = n * m - (m + n - 1)
		rest = 2 ** nr % 998244353
		p_c = path * color % 998244353
		p_c_r = p_c * rest % 998244353
		print(p_c_r)


from math import *
mod = 998244353

def fact(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p % mod

def powr(n):
	mod = 998244353
	ans = 1
	for i in range(n):
		ans = ans * 2 % mod
	return ans
for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = l[0]
	m = l[1]
	mod = 998244353
	if (n + m) % 2 == 1:
		ans = fact(n + m - 2, n - 1) * fact(n + m - 1, (n + m - 1) // 2) % mod * 2 ** (n * m - (n + m - 1)) % mod % mod
		print(ans)
	else:
		print(0)


import math
mod = 998244353
(n, m) = (1001, 1001)
dp = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
	for j in range(m):
		if i == 0 and j == 0:
			dp[i][j] = 1
		elif i == 0:
			dp[i][j] = dp[i][j - 1]
		elif j == 0:
			dp[i][j] = dp[i - 1][j]
		else:
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if (n + m) % 2 == 0:
		print(0)
		continue
	pathLen = m + n - 1

	def comb(x):
		return math.comb(x, x // 2)
	res = dp[n - 1][m - 1] * comb(pathLen) % mod
	po = n * m - n - m + 1
	res = res * pow(2, po, mod) % mod
	print(res)


import sys
import math
from collections import defaultdict, Counter
from itertools import permutations
from collections import deque

def sin():
	return int(sys.stdin.readline())

def array():
	return list(map(int, sys.stdin.readline().strip().split()))

def two():
	return map(int, sys.stdin.readline().strip().split())

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

def string():
	return sys.stdin.readline().strip()

def sqrt(x):
	(low, high) = (0, x)
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid + 1) * (mid + 1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
import sys
import bisect
import math
from collections import defaultdict, Counter
from itertools import permutations
from collections import deque

def sin():
	return int(sys.stdin.readline())

def array():
	return list(map(int, sys.stdin.readline().strip().split()))

def two():
	return map(int, sys.stdin.readline().strip().split())

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

def string():
	return sys.stdin.readline().strip()

def sqrt(x):
	(low, high) = (0, x)
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid + 1) * (mid + 1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
mod = 998244353

def modpow(a, b):
	ans = 1
	while b > 0:
		if b % 2:
			ans = ans * a % mod
		b = b // 2
		a = a % mod * (a % mod) % mod
	return ans
fact = [1] * 100001
for i in range(1, 100001):
	fact[i] = i * fact[i - 1]
	fact[i] %= mod
t = sin()
for _ in range(t):
	(n, m) = multiple()
	x = n + m - 1
	if x % 2:
		print(0)
	else:
		a = fact[x]
		b = modpow(fact[x // 2], mod - 2)
		c = modpow(fact[x - x // 2], mod - 2)
		way = 1
		way *= a
		way %= mod
		way *= b
		way %= mod
		way *= c
		way %= mod
		tot = n * m
		left = tot - x
		left_way = pow(2, left, mod)
		a = fact[n + m - 2]
		b = modpow(fact[m - 1], mod - 2)
		c = modpow(fact[n + m - 2 - (m - 1)], mod - 2)
		tot_way = 1
		tot_way *= a
		tot_way %= mod
		tot_way *= b
		tot_way %= mod
		tot_way *= c
		tot_way %= mod
		print(way * tot_way * left_way % mod)


MOD = 998244353
fact = [1, 1]
for i in range(2, 2005):
	fact.append(fact[i - 1] * i % MOD)

def solve(a, b):
	l = a + b - 1
	if l % 2 == 1:
		print(0)
		return
	res = fact[l - 1]
	res *= pow(fact[a - 1], MOD - 2, MOD)
	res *= pow(fact[b - 1], MOD - 2, MOD)
	res *= pow(2, a * b - l, MOD)
	res *= fact[l]
	res *= pow(fact[l // 2], MOD - 2, MOD)
	res *= pow(fact[l // 2], MOD - 2, MOD)
	print(res % MOD)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	solve(a, b)


from math import factorial as f

def red_green_path(m, n):
	if (m + n - 1) % 2 != 0:
		return 0
	paths = f(m + n - 2) // (f(m - 1) * f(n - 1))
	path_colorings = f(m + n - 1) // f((m + n - 1) // 2) ** 2
	coloring_occurrences = 2 ** (m * n - (m + n - 1))
	return paths * path_colorings * coloring_occurrences % 998244353
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	r = red_green_path(m, n)
	print(r)


import math
tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	minimum = min(n, m)
	path_length = n + m - 1
	if path_length % 2 == 0:
		possiblities = math.comb(path_length, path_length // 2)
		others = n * m - path_length
		others_val = pow(2, others, 998244353)
		y = math.comb(n + m - 2, n - 1)
		print(y * possiblities * others_val % 998244353)
	else:
		print(0)


import math

def checkpowee(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def findyuvi(mans1, nifgiwugf):
	return math.comb(mans1 + nifgiwugf - 2, mans1 - 1)
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	flag = a + b - 1
	if flag % 2 == 1:
		print(0)
		continue
	MOD = 998244353
	(var, var22) = (1, 1)
	ans = findyuvi(a, b) % MOD
	yuvii = b * a - flag
	yuvii = checkpowee(2, yuvii, MOD)
	for j in range(1, flag + 1):
		if j <= flag // 2:
			var *= j
		else:
			var22 *= j
	print(var22 // var % MOD * ans % MOD * yuvii % MOD)


def nCr(n, r):
	ans = 1
	for i in range(1, r + 1):
		ans = ans * (n - i + 1) // i
	return ans
for _ in range(int(input())):
	s = input().split()
	(n, m) = map(int, s)
	if (n + m) % 2 == 0:
		ans = 0
	else:
		paths = nCr(n + m - 2, n - 1)
		pathLength = nCr(n + m - 1, (n + m - 1) // 2)
		ans = paths * pathLength * 2 ** (n * m - (n + m - 1)) % 998244353
	print(ans)


def findCom(n, r):
	res = 1
	r = min(r, n - r)
	for i in range(1, r + 1):
		res = res * n // i
		n -= 1
	return res
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mod = 998244353
	totalCells = n * m
	pathLength = n + m - 1
	if pathLength % 2 != 0:
		print(0)
		continue
	ans = 0
	paths = findCom(pathLength - 1, n - 1) % mod
	remainingCells = totalCells - pathLength
	a = findCom(pathLength, pathLength // 2) % mod
	b = pow(2, remainingCells, 998244353)
	print(paths * a * b % mod)


import math
from operator import mod
import pathlib
t = int(input())

def powers(cells):
	batches = cells // 100
	rem = cells % 100
	ans = 1
	for i in range(batches):
		ans = ans * int(math.pow(2, 100)) % 998244353
	ans = ans * int(math.pow(2, rem)) % 998244353
	return ans
for _ in range(t):
	(n, m) = map(int, input().split())
	pathLen = m + n - 1
	if not pathLen % 2:
		paths = int(math.comb(pathLen - 1, n - 1)) % 998244353
		greens = pathLen // 2
		pathCombo = int(math.comb(pathLen, greens)) % 998244353
		cells = n * m - pathLen
		gridCombo = powers(cells)
		ans = paths * gridCombo * pathCombo % 998244353
		print(ans)
	else:
		print(0)


import sys
import math
import collections
import random
from heapq import heappush, heappop
from functools import reduce
input = lambda : sys.stdin.readline().rstrip('\r\n')
ints = lambda : list(map(int, input().split()))
MOD = 998244353

def solve() -> None:
	(n, m) = map(int, input().split())
	k = n + m - 1
	if k & 1:
		print(0)
		return

	def comb(n: int, k: int, m=1) -> int:
		res = 1
		for i in range(1, k + 1):
			res = res * (n - i + 1) // i
		return res
	ans = comb(k, k // 2, MOD)
	ans *= pow(2, n * m - k, MOD)
	ans %= MOD
	k = min(n - 1, m - 1)
	ans *= comb(n + m - 2, k, MOD)
	ans %= MOD
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import *
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	M = 998244353
	print(comb(n + m - 2, n - 1) * comb(n + m - 1, (n + m - 1) // 2) * 2 ** (n * m - (n + m - 1)) * bool((n + m - 1) % 2 == 0) % M)


import math
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = n + m - 1
	b = n * m - a
	s = 0
	if (n + m) % 2 != 0:
		p = math.comb(n + m - 2, n - 1)
		c = math.comb(a, a // 2)
		r = 2 ** b
		s = p * c * r % 998244353
	print(s)


mod = 998244353
a = [[0 for i in range(2001)] for i in range(2001)]
for i in range(2001):
	a[i][0] = 1
for i in range(1, 2001):
	for j in range(1, i + 1):
		a[i][j] = (a[i - 1][j] + a[i - 1][j - 1]) % mod
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = n + m - 1
	if l % 2:
		print(0)
	else:
		print(int(a[n + m - 2][m - 1] * a[l][l // 2] * 2 ** (n * m - l) % mod) % mod)


import math
t = int(input())
while t > 0:
	(n, m) = list(map(int, input().split()))
	x = 0
	a = n + m - 1
	b = n * m - a
	if (n + m) % 2 != 0:
		x = math.comb(a, int(a / 2))
		y = math.comb(a - 1, n - 1)
		z = pow(2, b)
		x = x * y * z
		x = x % 998244353
	print(x)
	t = t - 1


dp = [[0] * 2005 for i in range(2005)]
MOD = 998244353
for i in range(2005):
	dp[i][0] = 1
for i in range(1, 2005):
	for j in range(1, i + 1):
		dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = dp[n + m - 2][n - 1] * dp[n + m - 1][(n + m - 1) // 2] * pow(2, n * m - n - m + 1, MOD) % MOD
	if (n + m - 1) % 2 != 0:
		ans = 0
	print(ans)


import math
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	if (n + m - 1) % 2 == 1:
		print(0)
		continue
	print(math.comb(n + m - 2, n - 1) * math.comb(n + m - 1, (n + m - 1) // 2) * 2 ** (n * m - (n + m - 1)) % 998244353)


import time
import sys
import math

def get_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
input = sys.stdin.readline
(mod, infi) = (998244353, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from heapq import heappop, heappush, heapify
from itertools import accumulate
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
normal = lambda : input().split()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)

def solve(n, m):
	no_of_paths = math.comb(m + n - 2, m - 1)
	l = n + m - 1
	res = math.comb(l, l >> 1)
	return no_of_paths * res * pow(2, n * m - l, mod) % mod
T = inty()
for _ in range(T):
	(n, m) = mappy()
	if n + m - 1 & 1:
		print(0)
		continue
	print(solve(n, m))


import math
for T in range(int(input())):
	(n, m) = [eval(i) for i in input().split()]
	ans = 0
	l = int(m + n - 1)
	if l % 2 != 0:
		print(0)
		continue
	if l % 2 == 0 and m > 1:
		ans = ans + math.comb(n + m - 2, m - 1) * math.comb(l, int(l / 2)) * pow(2, n * m - l, 998244353)
	if l % 2 == 0 and m == 1:
		ans = ans + math.comb(n + m - 2, n - 1) * math.comb(l, int(l / 2)) * pow(2, n * m - l, 998244353)
	print(ans % 998244353)


import math
for q in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	l = int(m + n - 1)
	if l % 2 != 0:
		print(0)
		continue
	if l % 2 == 0 and m > 1:
		ans = ans + math.comb(n + m - 2, m - 1) * math.comb(l, int(l / 2)) * pow(2, n * m - l, 998244353)
	if l % 2 == 0 and m == 1:
		ans = ans + math.comb(n + m - 2, n - 1) * math.comb(l, int(l / 2)) * pow(2, n * m - l, 998244353)
	print(ans % 998244353)


import math

def numberOfPaths(m, n):
	path = 1
	for i in range(n, m + n - 1):
		path *= i
		path //= i - n + 1
	return path
for _ in range(int(input())):
	a = list(map(int, input().strip().split()))
	if (a[1] + a[0]) % 2 == 0:
		print(0)
	else:
		b = numberOfPaths(a[0], a[1])
		x = a[0] * a[1] - (a[0] + a[1] - 1)
		ans = pow(2, x, 998244353)
		ans *= math.comb(a[0] + a[1] - 1, (a[0] + a[1] - 1) // 2)
		print(ans * b % 998244353)


from math import comb
test = int(input())
while test:
	(row, col) = map(int, input().split())
	print(0) if (row + col - 1) % 2 else print(2 ** (row * col - (row + col - 1)) % 998244353 * (comb(row + col - 1, (row + col - 1) // 2) % 998244353) * (comb(row + col - 2, row - 1) % 998244353) % 998244353)
	test -= 1


import math
for _ in range(int(input())):
	a = list(map(int, input().strip().split()))
	if (a[1] + a[0]) % 2 == 0:
		print(0)
	else:
		x = a[0] * a[1] - (a[0] + a[1] - 1)
		ans = pow(2, x, 998244353) * math.comb(a[0] + a[1] - 2, a[1] - 1)
		ans *= math.comb(a[0] + a[1] - 1, (a[0] + a[1] - 1) // 2)
		print(ans % 998244353)


mod = 998244353

def nPaths(n, m):
	return mult2(m + n - 2) * (pow(mult2(n - 1), mod - 2, mod) * pow(mult2(m - 1), mod - 2, mod) % mod) % mod

def mult1(n):
	ans = 1
	for i in range(n, n // 2, -1):
		ans = ans * i % mod
	return ans

def mult2(n):
	ans = 1
	for i in range(n, 0, -1):
		ans = ans * i % mod
	return ans
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	N = n + m - 1
	if N & 1:
		ans = 0
	else:
		numPaths = nPaths(n, m)
		ans = pow(2, n * m - N, mod) * (numPaths * (mult1(N) * pow(mult2(N // 2), mod - 2, mod)) % mod) % mod % mod
	print(ans)


from math import *
M = 998244353

def printNcR(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p

def solve(n, m):
	l = n + m - 1
	if l % 2 != 0:
		return 0
	value1 = printNcR(m + n - 2, m - 1)
	value2 = printNcR(m + n - 1, (m + n - 1) // 2)
	value3 = 2 ** ((m - 1) * (n - 1))
	return value1 * value2 * value3 % M
for t in range(int(input())):
	(n, m) = map(int, input().split())
	print(solve(n, m))


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
N = 1000000
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
p = 998244353
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
import sys
sys.setrecursionlimit(1000000)
n = 1005
m = 1005
count = [[0 for x in range(n)] for y in range(m)]
for i in range(m):
	count[i][0] = 1
for j in range(n):
	count[0][j] = 1
for i in range(1, m):
	for j in range(1, n):
		count[i][j] = (count[i - 1][j] + count[i][j - 1]) % 998244353

def permu(n, r, p):
	global fact
	return Binomial(n, r, p) * fact[r] % 998244353
for _ in range(int(input())):
	(n, m) = mi()
	if (n + m - 1) % 2 == 1:
		print(0)
		continue
	d = n + m - 1
	total = n * m
	ans = count[n - 1][m - 1] * Binomial(d, d // 2, p) % 998244353 * pow(2, total - d, p)
	print(ans % 998244353)


def modInverse(A, M):
	g = gcd(A, M)
	if g != 1:
		print("Inverse doesn't exist")
	else:
		return power(A, M - 2, M)

def power(x, y, M):
	if y == 0:
		return 1
	p = power(x, y // 2, M) % M
	p = p * p % M
	if y % 2 == 0:
		return p
	else:
		return x * p % M

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def uniquePaths(m, n):
	path = 1
	for i in range(n, m + n - 1):
		path *= i
		path //= i - n + 1
	return path
from math import comb
test = int(input())
for k in range(test):
	(n, m) = map(int, input().split())
	val = uniquePaths(m, n)
	num = n + m - 1
	if num % 2 != 0:
		print(0)
		continue
	result = 1
	div = 1
	mid = int(num / 2)
	for i in range(1, num + 1):
		if i <= mid:
			div *= i
			div %= 998244353
		else:
			result *= i
			result %= 998244353
	result *= modInverse(div, 998244353)
	result %= 998244353
	mul = m * n - num
	nmul = power(2, mul, 998244353)
	result *= nmul
	result %= 998244353
	result *= val
	result %= 998244353
	print(result)


def power(x, y, p):
	res = 1
	while y > 0:
		if y & 1 != 0:
			res = res * x
		y = y >> 1
		x = x * x
	return res % p

def fun(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
for z in range(0, t):
	p = 998244353
	(n, m) = map(int, input().split())
	if (n + m - 1) % 2 == 1:
		print(0)
	else:
		path = fun(n + m - 2, n - 1, p)
		matrix = fun(n + m - 1, (n + m - 1) // 2, p)
		res = power(2, n * m - (n + m - 1), p)
		ans = path * matrix * res % p
		print(ans)


import math

def uniquePaths(m, n):
	return math.comb(m + n - 2, m - 1)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	check = m + n - 1
	if check % 2 == 1:
		print(0)
		continue
	M = 998244353
	path = uniquePaths(n, m) % M
	rem = m * n - check
	rem = power(2, rem, M)
	(temp1, temp2) = (1, 1)
	for i in range(1, check + 1):
		if i <= check // 2:
			temp1 *= i
		else:
			temp2 *= i
	print(temp2 // temp1 % M * path % M * rem % M)


import math

def bpow(a, n):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * a
			n -= 1
		else:
			a = a * a
			n = n // 2
	return res
t = int(input())
for t in range(t):
	(n, m) = map(int, input().split())
	if (n + m) % 2 == 0:
		print(0)
	else:
		print(math.comb(n + m - 2, n - 1) * bpow(2, n * m - (n + m - 1)) * math.comb(n + m - 1, (n + m - 1) // 2) % 998244353)


from math import *
mod = 998244353

def ncr(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p = p // m % mod
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p
test = int(input())
while test:
	(n, m) = map(int, input().split())
	if (m + n - 1) % 2:
		print(0)
	else:
		print(2 ** (n * m - (n + m - 1)) * ncr(m + n - 1, (m + n - 1) // 2) * ncr(m + n - 2, n - 1) % mod)
	test -= 1


N = 1000
M = 1000
mod = 998244353

def binomialCoeff(n, r):
	m = 998244353
	inv = [0 for _ in range(r + 1)]
	inv[0] = 1
	if r + 1 >= 2:
		inv[1] = 1
	for i in range(2, r + 1):
		inv[i] = m - m // i * inv[m % i] % m
	ans = 1
	for i in range(2, r + 1):
		ans = ans % m * (inv[i] % m) % m
	for i in range(n, n - r, -1):
		ans = ans % m * (i % m) % m
	return ans
dp = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
	for j in range(M):
		if i == 0 or j == 0:
			dp[i][j] = 1
		else:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
			dp[i][j] %= mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if (n + m - 1) % 2:
		print(0)
		continue
	k = n * m - (n + m - 1)
	left = pow(2, k, mod)
	ways = dp[n - 1][m - 1]
	colors = binomialCoeff(n + m - 1, (n + m - 1) // 2)
	print(left * ways * colors % mod)


f = {0: 1, 1: 1}

def factorial(n):
	if n in f:
		return f[n]
	x = n
	for i in range(n - 1, 0, -1):
		if i in f:
			x = x * f[i]
			break
		else:
			x = x * i
	f[n] = x
	return f[n]
for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	if (n + m - 1) % 2 == 1:
		print(0)
	else:
		a = factorial(n + m - 2) // (factorial(n - 1) * factorial(m - 1))
		b = factorial(n + m - 1) // (factorial((n + m - 1) // 2) * factorial((n + m - 1) // 2))
		c = 2 ** (n * m - n - m + 1)
		print(a * b * c % 998244353)


import math

def fpw(a, n, r):
	if n == 0:
		return 1
	x = fpw(a, n // 2, r) % r
	x = x * x % r
	if n % 2 == 1:
		x = x * a % r
	return x
t = int(input())
while t > 0:
	[n, m] = [int(x) for x in input().split()]
	if (n + m - 1) % 2 == 0:
		a = fpw(2, n * m - n - m + 1, 998244353)
		b = int(math.comb(n + m - 1, (n + m - 1) // 2)) % 998244353
		c = int(math.comb(n + m - 2, n - 1)) % 998244353
		ans = a * b % 998244353
		ans = ans * c % 998244353
		print(ans % 998244353)
	else:
		print(0)
	t = t - 1


from math import comb, factorial
for i in range(int(input())):
	(n, m) = map(int, input().split(' '))
	mod = 998244353
	x = (n + m - 1) % mod
	if x % 2 == 0:
		val = comb((m + n - 2) % mod, (n - 1) % mod) % mod
		poww = 2 ** (n * m % mod - x) % mod % mod
		com = comb(x, x // 2) % mod
		res = val * poww % mod * com % mod
		print(res)
	else:
		print(0)


from math import factorial as fact
for a0 in range(int(input())):
	(n, m) = map(int, input().split())
	mod = 998244353
	a1 = fact(n + m - 2) // (fact(n - 1) * fact(m - 1))
	z = n + m
	if z % 2:
		a2 = fact(z - 1) // pow(fact((z - 1) // 2), 2)
		print(a1 * a2 * pow(2, n * m - (n + m - 1)) % mod)
	else:
		print(0)


from math import comb
n1 = int(input())
for i in range(n1):
	x = [int(a) for a in input().split()]
	n = x[0]
	m = x[1]
	if (n + m - 1) % 2 == 1:
		print(0)
	else:
		a1 = comb(n + m - 1, (n + m - 1) // 2)
		a2 = pow(2, n * m - n - m + 1)
		a3 = comb(n + m - 2, n - 1)
		print(int(a1 * a2 * a3) % 998244353)


mod_ = 10 ** 9 + 7
mod_ = 998244353
a = [1] * 2010
for i in range(2, 2010):
	a[i] = i * a[i - 1]
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	x = n + m - 1
	if n == 1 and m == 1:
		print(0)
		continue
	if x % 2:
		print(0)
		continue
	ways = pow(2, m * n - x, mod_)
	x //= 2
	comb = a[2 * x] // (a[x] * a[x]) % mod_
	paths = a[n + m - 2] // (a[n - 1] * a[m - 1]) % mod_
	count = ways * comb * paths % mod_
	print(count)


import sys
input = sys.stdin.readline
from math import sqrt
from collections import defaultdict

def I():
	return list(map(int, input().split()))
mod = 998244353
lim = 2 * 10 ** 3 + 10
numberOfPaths = [[1] * lim for i in range(lim)]
for i in range(1, lim):
	for j in range(1, lim):
		numberOfPaths[i][j] = numberOfPaths[i - 1][j] + numberOfPaths[i][j - 1]
		numberOfPaths[i][j] %= mod
f = [1] * lim
inv_f = [1] * lim
for i in range(2, lim):
	f[i] = f[i - 1] * i
	f[i] %= mod
	inv_f[i] = pow(f[i], mod - 2, mod)
for _ in range(int(input())):
	(n, m) = I()
	l = n + m - 1
	if l % 2:
		print(0)
		continue
	tp = numberOfPaths[n - 1][m - 1]
	path_comb = f[l] * inv_f[l // 2] * inv_f[l // 2]
	path_comb %= mod
	out_l = n * m - l
	out_comb = 1
	if out_l != 0:
		out_comb = pow(2, out_l, mod)
	print(tp * path_comb * out_comb % mod)


import math
modulo = 998244353
fac_buffer = [math.factorial(i) % modulo for i in range(2000)]

def factorial(x):
	return fac_buffer[x]

def readline():
	return list(map(int, input().split()))

def get_permutation(p, k):
	assert p >= k
	result = factorial(p) * pow(factorial(k), -1, modulo) * pow(factorial(p - k), -1, modulo)
	return result % modulo
for _ in range(int(input())):
	(N, M) = readline()
	path_len = N + M - 1
	if path_len % 2 == 1:
		print(0)
		continue
	path_arrangements = get_permutation(path_len, path_len // 2)
	leftover_spaces = N * M - path_len
	leftover_arrangements = pow(2, leftover_spaces, modulo)
	shape_size = N + M - 2
	shape_arrangements = get_permutation(shape_size, N - 1)
	result = 1
	arrangements = [path_arrangements, leftover_arrangements, shape_arrangements]
	for i in arrangements:
		result *= i
		result %= modulo
	print(result)


import math
from functools import reduce
import sys
sys.setrecursionlimit(1000000)

def read(func=str, sep=None):
	return list(map(func, input().split(sep)))

def read_ints(sep=None):
	return read(func=int, sep=sep)

def read_int():
	return int(input())

def print_array(arr, sep=' '):
	print(sep.join(map(str, arr)))

def bitcount(num):
	bits = 0
	while num:
		if num & 1:
			bits += 1
		num >>= 1
	return bits

def highest_bit(n):
	count = 0
	while n != 0:
		count += 1
		n >= 1
	return count - 1

def modpow(num, pow, mod):
	if pow == 0:
		return 1
	c = modpow(num, pow // 2, mod)
	if pow & 1:
		return c ** 2 % mod * num % mod
	else:
		return c ** 2 % mod
test_cases = read_int()
mod = 998244353
ncr_memo = {}

def ncr(n, r):
	if n < r:
		return 0
	if r == 0:
		return 1
	if n == 1:
		return 1
	if r == 1:
		return n
	if (n, r) in ncr_memo:
		return ncr_memo[n, r]
	ncr_memo[n, r] = ncr(n - 1, r) + ncr(n - 1, r - 1)
	return ncr_memo[n, r]

def modpow(n, pow, mod):
	if pow == 0:
		return 1
	if pow == 1:
		return n % mod
	x = modpow(n, pow // 2, mod)
	if pow & 1:
		return x * x % mod * n % mod
	else:
		return x * x % mod
memo = {}
for _ in range(test_cases):
	(n, m) = read_ints()
	x = n + m - 1
	comb = ncr(x, x // 2) * modpow(2, n * m - x, mod) % mod

	def dp(i, j):
		if i < 1 or j < 1:
			return 0
		if i == 1 and j == 1:
			return 1
		if (i, j) in memo:
			return memo[i, j]
		out = dp(i - 1, j) % mod + dp(i, j - 1) % mod
		out %= mod
		memo[i, j] = out
		return out
	if n + m - 1 & 1:
		print(0)
	else:
		print(dp(n, m) * comb % mod)


def fact(n):
	if n == 0:
		return 1
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans
t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	if (a + b - 1) % 2:
		print(0)
	else:
		valid = fact(a + b - 2) // (fact(a - 1) * fact(b - 1))
		n = a + b - 1
		m = a * b - n
		n = fact(n) // (fact(n // 2) * fact(n - n // 2))
		ans = valid * n * 2 ** m % 998244353
		print(ans)


from math import comb

def solve(a, b, mod=998244353):
	l = a + b - 1
	if l % 2:
		return 0
	return pow(2, a * b - l, mod) * comb(l, l // 2) * comb(l - 1, a - 1) % mod
for _ in range(int(input())):
	(a, b) = map(int, input().strip().split())
	print(solve(a, b))


import sys
sys.setrecursionlimit(10 ** 8)
N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans

def moduloExponentiation(x, n, mod):
	ans = 1
	while n > 0:
		if n % 2 == 1:
			ans = ans * x % mod
		x = x * x % mod
		n = n // 2
	return ans
p = 998244353
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for dkfkdhfkhiehfdihfuksdk in range(int(input())):
	(n, m) = map(int, input().split())
	steps = n + m - 1
	mod = 998244353
	if steps % 2 == 1:
		print(0)
		continue
	else:
		pathValues = Binomial(steps, steps // 2, mod) % mod
		numOfTimes = moduloExponentiation(2, n * m - steps, mod) % mod
		numOfPath = Binomial(n - 1 + (m - 1), n - 1, mod) % mod
		ans = pathValues * numOfTimes % mod * numOfPath % mod
		print(ans)