AtCoder Grand Contest 036 - GP 2

We have a sequence of N integers: x=(x_0,x_1,\cdots,x_{N-1}). Initially, x_i=0 for each i (0 \leq i \leq N-1).

Snuke will perform the following operation exactly M times:

* Choose two distinct indices i, j (0 \leq i,j \leq N-1,\ i \neq j). Then, replace x_i with x_i+2 and x_j with x_j+1.



Find the number of different sequences that can result after M operations. Since it can be enormous, compute the count modulo 998244353.

Constraints

* 2 \leq N \leq 10^6
* 1 \leq M \leq 5 \times 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of different sequences that can result after M operations, modulo 998244353.

Examples

Input

2 2


Output

3


Input

3 2


Output

19


Input

10 10


Output

211428932


Input

100000 50000


Output

3463133

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, m) = map(int, input().split())
(w, u) = (3 * m, n - 1)
(o, f, i) = (998244353, [1], 1)
while i < w + n:
	f += [f[-1] * i % o]
	i += 1
c = lambda n, k=u: f[n] * pow(f[n - k], o - 2, o) * pow(f[k], o - 2, o)
a = c(w + u) - n * c(n + m - 2)
while ~-n > m < w:
	m += 2
	a -= c(n, m) * c(2 * u + w - m >> 1)
print(a % o)


(N, M) = map(int, input().split())
MOD = 998244353
if N < M:
	one = N - (N - M) % 2
	two = (3 * M - one) // 2
else:
	(one, two) = (M, M)
L = M + M // 2 + N - 1
fac = [0] * (L + 1)
inv = [0] * (L + 1)
(fac[0], inv[0]) = (1, 1)
for i in range(1, L + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv[i] = pow(fac[i], MOD - 2, MOD)

def comb(n, r):
	if n <= 0 or r < 0:
		return 0
	return fac[n] * inv[n - r] * inv[r] % MOD
ret = 0
while one >= 0:
	ret += comb(N, one) * comb(two + N - 1, N - 1) % MOD
	ret %= MOD
	one -= 2
	two += 1
ret -= comb(3 * M + N - 1 - (2 * M + 1), N - 1) * N
print(ret % MOD)


def modfac(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)

def modnCr(n, r, mod, fac, inv):
	if n < r:
		return 0
	return fac[n] * inv[n - r] * inv[r] % mod
mod = 998244353
(N, M) = map(int, input().split())
(fac, inv) = modfac(N + 3 * M + 10, mod)
ans = modnCr(3 * M + N - 1, N - 1, mod, fac, inv)
for k in range(M + 1, N + 1):
	if (3 * M - k) % 2 == 0:
		ans -= modnCr(N, k, mod, fac, inv) * modnCr((3 * M - k) // 2 + N - 1, N - 1, mod, fac, inv)
		ans %= mod
for k in range(M + 1):
	if (3 * M - k) % 2 == 0:
		amari = (3 * M - (k + 2 * M)) // 2
		now = modnCr(N, k, mod, fac, inv) * k * modnCr(amari + N - 1, N - 1, mod, fac, inv)
		amari -= 1
		now += modnCr(N, k, mod, fac, inv) * (N - k) * modnCr(amari + N - 1, N - 1, mod, fac, inv)
		ans -= now
		ans %= mod
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
mod = 998244353
inv = [0] * (3 * M // 2 + N + 2)
inv[1] = 1
for i in range(2, 3 * M // 2 + N + 2):
	inv[i] = -(mod // i) * inv[mod % i] % mod
g1 = [1, 1]
g2 = [1, 1]
for i in range(2, 3 * M // 2 + N + 2):
	num_1 = g1[-1] * i % mod
	g1.append(num_1)
	g2.append(g2[-1] * inv[i] % mod)

def cmb(n, r):
	return g1[n] * g2[r] * g2[n - r] % mod
ans = 0
for i in range(min(N + 1, M + 1)):
	if M % 2 != i % 2:
		continue
	m = (3 * M - i) // 2
	num = (cmb(m + N - 1, N - 1) - i * cmb(m - M + N - 1, N - 1)) % mod
	if m >= M + 1:
		num = (num - (N - i) * cmb(m - M + N - 2, N - 1)) % mod
	ans = (ans + cmb(N, i) * num) % mod
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)
INF = 10 ** 15

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353
(n, m) = LI()
a = n + 3 * m
fac = [1] * (a + 1)
inv = [1] * (a + 1)
for j in range(1, a + 1):
	fac[j] = fac[j - 1] * j % mod
inv[a] = pow(fac[a], mod - 2, mod)
for j in range(a - 1, -1, -1):
	inv[j] = inv[j + 1] * (j + 1) % mod

def comb(x, y):
	if y > x or x < 0 or y < 0:
		return 0
	return fac[x] * inv[x - y] * inv[y] % mod
ans = 0
for i in range(min(m + 1, n + 1)):
	if (m - i) % 2:
		continue
	ans += comb(n, i) * comb((m * 3 - i) // 2 + n - 1, n - 1)
	ans %= mod
print((ans - n * comb(m - 1 + n - 1, n - 1)) % mod)


(n, m) = map(int, input().split())
mod = 998244353
max = n + 2 * m + 100
(fac, finv, inv) = ([0] * max, [0] * max, [0] * max)

def comInit(max):
	fac[0] = fac[1] = 1
	finv[0] = finv[1] = 1
	inv[1] = 1
	for i in range(2, max):
		fac[i] = fac[i - 1] * i % mod
		inv[i] = mod - inv[mod % i] * (mod // i) % mod
		finv[i] = finv[i - 1] * inv[i] % mod
comInit(max)

def com(n, k):
	if n < k:
		return 0
	if (n < 0) | (k < 0):
		return 0
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
a = 0
for x in range(min(m, n) + 1):
	if (3 * m - x) % 2 == 1:
		continue
	y = (3 * m - x) // 2
	a += com(n, x) * fac[y + n - 1] * finv[y] * finv[n - 1]
	a %= mod
b = fac[n - 1 + m - 1] * finv[n - 1] * finv[m - 1] * n
b %= mod
ans = a - b
ans %= mod
print(ans)


(n, m) = map(int, input().split())
(o, f, i) = (998244353, [1], 1)
while i < 3 * m + n:
	f += [f[-1] * i % o]
	i += 1
c = lambda x, y=n - 1: f[x] * pow(f[x - y] * f[y] % o, o - 2, o)
a = c(-1) - n * c(n + m - 2)
while ~-n > m < i - n:
	m += 2
	a -= c(n, m) * c(n - 1 + i - m >> 1)
print(a % o)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

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

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

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)

def A():
	n = I()
	if n <= 1000000000:
		print(0, 0, 1, 0, 0, n)
	else:
		b = 1000000000
		a = 1
		y = -n % 1000000000
		x = (n + a * y) // b
		print(0, 0, x, y, a, b)
		return
	return

def B():
	(n, k) = LI()
	a = LI()
	s = []
	f = [1] * 1000000
	for i in range(k):
		for j in range(n):
			aj = a[j]
			if f[aj]:
				s.append(aj)
				f[aj] = 0
			else:
				while 1:
					x = s.pop(-1)
					f[x] = 1
					if x == aj:
						break
		print(i + 1, s)
	return
mod = 998244353

def C():

	def comb(a, b):
		if a < b:
			return 1
		return fact[a] * inv[b] * inv[a - b] % mod
	(n, m) = LI()
	MA = 3 * m + max(n, 2 * m) - 1
	fact = [1] * (MA + 1)
	for i in range(MA):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv = [1] * (MA + 1)
	inv[MA] = pow(fact[MA], mod - 2, mod)
	for i in range(MA)[::-1]:
		inv[i] = inv[i + 1] * (i + 1) % mod
	ans = 0
	for k in range(min(m, n) + 1):
		if (3 * m - k) % 2 == 0:
			ans += comb(n, k) * comb((3 * m - k) // 2 + n - 1, n - 1)
			ans %= mod
	ans -= n * comb(3 * m - (2 * m + 1) + n - 1, n - 1)
	ans %= mod
	print(ans)
	return

def D():
	return

def E():
	n = I()
	return

def F():
	n = I()
	return
C()


from functools import lru_cache

def prepare(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)

def get_nhr(n, facts, invs):

	@lru_cache(maxsize=None)
	def nhr(r):
		return facts[n + r - 1] * invs[r] * invs[n - 1] % MOD
	return nhr
MOD = 998244353
(n, m) = list(map(int, input().split()))
(facts, invs) = prepare(n + 3 * m, MOD)
nhr = get_nhr(n, facts, invs)
ans = 0
for odd in range(m % 2, min(m, n) + 1, 2):
	tmp = nhr((3 * m - odd) // 2)
	if odd > 0:
		tmp -= odd * nhr((m - odd) // 2)
	if odd < n and odd <= m - 2:
		tmp -= (n - odd) * nhr((m - odd - 2) // 2)
	ans = (ans + facts[n] * invs[odd] * invs[n - odd] % MOD * tmp) % MOD
print(ans)


class comb:
	F = [1, 1]
	Fi = [1, 1]
	I = [0, 1]

	def __init__(self, num, mod):
		self.MOD = mod
		for i in range(2, num + 1):
			self.F.append(self.F[-1] * i % mod)
			self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
			self.Fi.append(self.Fi[-1] * self.I[i] % mod)

	def com(self, n, k):
		if n < k:
			return 0
		if n < 0 or k < 0:
			return 0
		return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD
(N, M) = list(map(int, input().split()))
MOD = 998244353
com = comb(M * 3 + N, MOD)
t = com.com(M * 3 + N - 1, N - 1)
t -= com.com(M - 1 + N - 1, N - 1) * N
while t < 0:
	t += MOD
if N > M:
	for k in range(M + 2, N + 1, 2):
		i = (M * 3 - k) // 2
		t -= com.com(N, k) * com.com(N - 1 + i, i) % MOD
	while t < 0:
		t += MOD
print(t)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 998244353
(N, M) = list(map(int, sys.stdin.readline().split()))

def get_factorials(max, mod=None):
	ret = [1]
	n = 1
	if mod:
		for i in range(1, max + 1):
			n *= i
			n %= mod
			ret.append(n)
	else:
		for i in range(1, max + 1):
			n *= i
			ret.append(n)
	return ret

def mod_invs(max, mod):
	invs = [1] * (max + 1)
	for x in range(2, max + 1):
		invs[x] = -(mod // x) * invs[mod % x] % mod
	return invs
factorials = get_factorials(M * 3 // 2 + N, MOD)
finvs = []
inv = 1
for i in mod_invs(M * 3 // 2 + N, MOD):
	inv = inv * i % MOD
	finvs.append(inv)

def ncr(n, r, mod=None):
	if n < r:
		return 0
	return factorials[n] * finvs[r] * finvs[n - r] % mod
c1 = 0
for odds in range(M * 3 % 2, M + 1, 2):
	half = (M * 3 - odds) // 2
	c1 += ncr(half + N - 1, N - 1, MOD) * ncr(N, odds, MOD)
	c1 %= MOD
c2a = 0
c2b = 0
for odds in range(M % 2, M + 1, 2):
	half = (M - odds) // 2
	c2a += ncr(half + N - 1, N - 1, MOD) * ncr(N, odds, MOD)
	c2a %= MOD
	c2b += ncr(half + N - 2, N - 2, MOD) * ncr(N - 1, odds, MOD)
	c2b %= MOD
c2 = (c2a - c2b) * N
print((c1 - c2) % MOD)


from collections import defaultdict

class Combination:

	def __init__(self, n, mod):
		self.n = n
		self.mod = mod
		self.fact = self.make_fact(n)
		self.fact_inv = self.make_fact_inv(n)

	def make_fact(self, n):
		res = [1] * (n + 1)
		for i in range(1, n + 1):
			res[i] = res[i - 1] * i % self.mod
		return res

	def make_fact_inv(self, n):
		fact_inv = [1] * (n + 1)
		fact_inv[n] = pow(self.fact[n], self.mod - 2, self.mod)
		for i in range(n, 0, -1):
			fact_inv[i - 1] = fact_inv[i] * i % self.mod
		return fact_inv

	def comb(self, m, k):
		if m < 0 or k < 0 or m < k:
			return 0
		return self.fact[m] * self.fact_inv[k] * self.fact_inv[m - k] % self.mod
mod = 998244353
(n, m) = map(int, input().split())
C = Combination(n + m * 3, mod)
ans = 0
for i in range(min(n, m) + 1):
	if m % 2 != i % 2:
		continue
	res = 0
	r = (m * 3 - i) // 2
	res += C.comb(r + n - 1, r)
	res -= C.comb(r - m - 1 + n - 1, n - 1) * (n - i)
	res -= C.comb(r - m + n - 1, n - 1) * i
	res *= C.comb(n, i)
	res % -mod
	ans += res
	ans %= mod
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
INF = float('inf')

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

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

def LS():
	return sys.stdin.readline().split()

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

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353
(n, m) = LI()
total = m * 3
fac = [1] * (total + n + 1)
inv = [1] * (total + n + 1)
for i in range(total + n):
	fac[i + 1] = fac[i] * (i + 1) % mod
inv[total + n] = pow(fac[-1], mod - 2, mod)
for j in range(total + n - 1, -1, -1):
	inv[j] = inv[j + 1] * (j + 1) % mod

def comb(n, r):
	if r > n:
		return 0
	return fac[n] * inv[n - r] * inv[r] % mod
ans = comb(total + n - 1, n - 1)
for i in range(m + 2, min(n + 1, total + 1)):
	if (total - i) % 2 == 0:
		ans -= comb(n, i) * comb(n + (total - i) // 2 - 1, n - 1) % mod
		ans %= mod
ret = 0
for i in range(m):
	ret = (ret + comb(i + n - 2, n - 2)) % mod
ans -= ret * n % mod
print(ans % mod)


def prepare(n, MOD):
	f = 1
	factorials = [1] * (n + 1)
	for m in range(1, n + 1):
		f = f * m % MOD
		factorials[m] = f
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv = inv * m % MOD
		invs[m - 1] = inv
	return (factorials, invs)

def get_nhr(n, facts, invs, MOD):

	def nhr(r):
		return facts[n + r - 1] * invs[r] * invs[n - 1] % MOD
	return nhr

def solve(n, m):
	MOD = 998244353
	(facts, invs) = prepare(n + 3 * m, MOD)
	fn = facts[n]
	nhr = get_nhr(n, facts, invs, MOD)
	nm2 = min(n, m - 1)
	ans = 0
	for odd in range(m % 2, min(m, n) + 1, 2):
		tmp = nhr((3 * m - odd) // 2)
		if odd > 0:
			tmp -= odd * nhr((m - odd) // 2)
		if odd < nm2:
			tmp -= (n - odd) * nhr((m - odd - 2) // 2)
		ans = (ans + fn * invs[odd] * invs[n - odd] % MOD * tmp) % MOD
	return ans
(n, m) = list(map(int, input().split()))
print(solve(n, m))