Problem:


Score : 900 points

Problem Statement

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.

Sample Input 1

2 2

Sample Output 1

3

After two operations, there are three possible outcomes:

x=(2,4)

x=(3,3)

x=(4,2)

For example, x=(3,3) can result after the following sequence of operations:

First, choose i=0,j=1, changing x from (0,0) to (2,1).

Second, choose i=1,j=0, changing x from (2,1) to (3,3).

Sample Input 2

3 2

Sample Output 2

19

Sample Input 3

10 10

Sample Output 3

211428932

Sample Input 4

100000 50000

Sample Output 4

3463133



Sample input:
2 2


Sample output:
3

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
mod = 998244353

#################################

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = n+3*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 = fac[n-1+3*m] * finv[n-1] * finv[3*m]
a %= mod
b = fac[n-1+m-1] * finv[n-1] * finv[m-1] * n
b %= mod
c = 0
for i in range(2*m+1,min(3*m,n)+1):
    c += fac[3*m-1]*finv[i-1]*finv[3*m-i]*com(n,i)
    c %= mod

d = 0
k = min(n,2*m)
for i in range(m+1,k+1):
    if(3*m-i)%2==1:
        continue
    l = (3*m-i)//2
    d += com(n,i) * fac[n+l-1]*finv[l]*finv[n-1]
    d %= mod

ans = a-b-c-d
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
mod = 998244353

#################################

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = n+3*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 = fac[n-1+3*m] * finv[n-1] * finv[3*m]
a %= mod
b = fac[n-1+m-1] * finv[n-1] * finv[m-1] * n
b %= mod
c = 0
for i in range(2*m+1,min(3*m,n)+1):
    c += fac[3*m-1]*finv[i-1]*finv[3*m-i]*com(n,i)
    c %= mod

d = 0
k = min(n,2*m)
for i in range(m+1,k+1):
    if(3*m-i)%2==1:
        continue
    l = (3*m-i)//2
    d += com(n,k) * com(k,i) * fac[k+l-1]*finv[l]*finv[k-1]
    d %= mod

ans = a-b-c-d
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n_ = 2500010
mod = 998244353

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = modinv(fun[n_], mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod
  
n, m = map(int, input().split())
ans = 0
for i in range(m%2, min(m, n) + 1, 2):
  ans = (ans + nCr(n, i) * (nCr((3*m-i)//2 + n - 1, n - 1) - 
      n * nCr((m-i)//2 + n - 1, n - 1))) % mod
for i in range(m%2, min(m, n-1) + 1, 2):
  ans = (ans - (n - 1) * nCr(n-1, i) * nCr((m-i)//2 + n - 2, n - 2)) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = 998244353
def inved(x):
  y = 1
  p = mod - 2
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y

fact = [1 for i in range(3*M+N)]
invf = [1 for i in range(3*M+N)]
for i in range(3*M+N-1):
  fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(3*M+N-1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
  
L = (fact[3*M+N-1] * invf[N-1] * invf[3*M]) % mod
R = (N * fact[M+N-2] * invf[N-1] * invf[M-1]) % mod

print((L - R) % mod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
MOD = 998244353

if N < M :
    one = 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)

Submission status: Wrong Answer

Solution code:
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 - 2)
    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))

Submission status: Wrong Answer

Solution code:
mod=998244353
import math

def f(n):
  return math.factorial(n)

def c(n,k):
  return f(n)//(f(n-k)*f(k))
n,m=map(int,input().split())

ans=c(3*m+n-1,n-1)
for i in range(1,m+1):
  ans-=c(3*m-(2*m+i)+n-2,n-2)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
n = 3*10**6+10
g1 = [1, 1]
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = cmb(M*3+N-1, N-1, mod)
for i in range(M*2+1, M*3+1):
    ans -= cmb(M*3-i+(N-1)-1, N-2, mod) * N + mod*mod
    ans = (ans+mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
MOD = 998244353

U = 4 * 10 ** 6
fact = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv = [1] * (U+1)
fact_inv[U] = pow(fact[U],MOD-2,MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if n == -1 and k == -1:
      return 1
    if n < 0:
      return 0
    if k < 0 or k > n:
      return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

answer = comb(3*M+N-1,N-1) # 何でもいいから作る
answer -= N * comb(M+N-2,N-1) # どれかが 2M+1 以上
answer %= MOD
# 「ちょうど1」がM個より多くある場合を引かなければいけない
# （既に引いた場合と背反）
for k in range(M+1,3*M+1):
    sgn = -1 if (k-M)%2 else 1
    # k個決める、残りは和が3M-k, 個数N-k
    x = comb(N,k)
    x *= comb(3*M-k+N-k-1,N-k-1)
    x %= MOD
    answer += sgn * x * comb(k-1,k-1-M) % MOD
    answer %= MOD
answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
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):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    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


factorials = get_factorials(M * 3 + N - 1, MOD)


# invs = mod_invs(M * 3 + N - 1, MOD)
# fi = [0, invs[1]]
# a = invs[1]
# for i in invs[2:]:
#     a = a * i % MOD
#     fi.append(a)
#
# print(invs)


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    return factorials[n] * mod_inv(factorials[r], mod) * mod_inv(factorials[n - r], mod) % mod


# 合計が M*3 となる数列の数
c1 = ncr(M * 3 + N - 1, N - 1, MOD)
# max が M*2 より大きい数列の数を引く
c2 = 0
for m in range(M * 2 + 1, M * 3 + 1):
    s = M * 3 - m
    c2 += ncr(s + N - 2, N - 2, MOD) * N
    c2 %= MOD
print((c1 - c2) % MOD)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
MOD = 998244353

U = 4 * 10 ** 6
fact = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv = [1] * (U+1)
fact_inv[U] = pow(fact[U],MOD-2,MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if n == -1 and k == -1:
      return 1
    if n < 0:
      return 0
    if k < 0 or k > n:
      return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

answer = comb(3*M+N-1,N-1) # 何でもいいから作る
answer -= N * comb(M+N-2,N-1) # どれかが 2M+1 以上

# 「ちょうど1」がM個より多くある場合を引かなければいけない
# （既に引いた場合と背反）
for k in range(M+1,3*M+1):
    sgn = -1 if (k-M)%2 else 1
    # k個決める、残りは和が3M-k, 個数N-k
    x = comb(N,k)
    x *= comb(3*M-k+N-k-1,N-k-1)
    answer += sgn * x * comb(k-1,k-1-M) % MOD
    answer %= MOD
answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
MOD = 998244353

U = 4 * 10 ** 6
fact = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv = [1] * (U+1)
fact_inv[U] = pow(fact[U],MOD-2,MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if n == -1 and k == -1:
      return 1
    if n < 0:
      return 0
    if k < 0 or k > n:
      return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % MOD

answer = comb(3*M+N-1,N-1) # 何でもいいから作る
answer -= N * comb(M+N-2,N-1) # どれかが 2M+1 以上

# 「ちょうど1」がM個より多くある場合を引かなければいけない
# （既に引いた場合と背反）
for k in range(M+1,3*M+1):
    sgn = -1 if (k-M)%2 else 1
    # k個決める、残りは和が3M-k, 個数N-k
    x = comb(N,k)
    x *= comb(3*M-k+N-k-1,N-k-1)
    answer += sgn * x * comb(k-1,k-1-M)
answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
p, q = map(int,input().split())
mod = 998244353


def comb(n,k):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = factorial(n) % mod
  b = factorial(k) % mod
  c = factorial(n - k) % mod
  return (a*power_func(b,mod-2)*power_func(c,mod-2))%mod
def power_func(a,b):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2)
    return d*d %mod
  if b%2==1:
    return (a*power_func(a,b-1))%mod

ans = comb(p+q*3-1, p-1)
now = 1
for i in range(q):
    if i == 0:
        ans -= now*p
    else:
        now = (now*(i+p-2)/i)%mod
        ans -= (now*p)%mod

print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
A = list(map(int, input().split())) 

n = A[0]
m = A[1]

print(n**m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
MOD = 998244353


def inverse(a,p):
    return pow(a,p-2,p)


data = [1,1]
append = data.append
q = 1
for i in range(2,3*m+n):
    q*=i
    q%=MOD
    append(q)


ans = data[3*m+n-1]*inverse(data[n-1],MOD)*inverse(data[3*m],MOD)
ans %=MOD
for i in range(m):
    ans -= data[n-2+i]*inverse(data[n-2],MOD)*inverse(data[i],MOD)*n
    ans %=MOD

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 998244353

def cmb(n, r):
    if r > n - r:
        r = n - r
    if r < 2:
        return n ** r

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = (result * numerator[k]) % mod
    return result

n, m = map(int, input().split())

print((cmb(3 * m + n - 1, n - 1) - n * cmb(m + n - 2, n - 1)) % mod)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
list_size = 2500100

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = (f_list[i] * (i + 2)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = (f_r_list[-i + 1] * (list_size + 2 - i)) % MOD

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n, m = map(int, input().split())
print((comb(3*m+n-1, n-1) - (n*(m+n-2)*comb(m+n-3, n-2)*pow(n-1, MOD-2, MOD))%MOD)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
mod=998244353
A=N+M*3
factl=[1]*(A)
invl=[1]*(A)
fv=1
for i in range(1,A):
    fv=fv*i%mod
    factl[i]=fv
    invl[i]=pow(fv,mod-2,mod)
ans=factl[A-1]*invl[N-1]*invl[M*3]%mod
Nm=N-1
for i in range(M):
    ans=(ans-factl[i+N-2]*invl[i]*invl[N-2]*N)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
mod=998244353
factl=[1]
invl=[1]
fv=1
for i in range(1,N+M*3):
    fv=fv*i%mod
    factl.append(fv)
    invl.append(pow(fv,mod-2,mod))
ans=factl[N+M*3-1]*invl[N-1]*invl[M*3]%mod
nc2=factl[N]*invl[N-2]*invl[2]%mod
ans=(ans-N-2*nc2*(M-1))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

U = 4*10**6
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m = map(int, input().split())
ans = 0
for k in range(m%2, min(n, m)+1, 2):
  ans += comb((3*m-k)//2+n-1, n-1) * comb(n, k)
  ans %= MOD
cnt = 0
for k in range(m):
  cnt += comb(k+n-2, n-2)
  cnt %= MOD
cnt *= n
cnt %= MOD
ans -= cnt
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod=998244353

MAX=3*M//2+N

inv=[0]*(MAX+1)
inv[1]=1
for i in range(2,MAX+1):
    inv[i]=-(mod//i)*inv[mod%i]%mod

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
mod=998244353

#階乗テーブル
g1=[1,1]
for i in range(2,3*M//2+N+2):
    g1.append(g1[-1]*i%mod)

def cmb(n,r):
    return g1[n]*pow(g1[r],mod-2,mod)*pow(g1[n-r],mod-2,mod)%mod

#奇数の和で場合分け
#iは奇数の数

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)

Submission status: Time Limit Exceeded

Solution code:
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)
inv = [1] * (total + n)
i = 1
for j in range(1, total + n):
    i = i * j % mod
    fac[j] = i
    inv[j] = pow(i, mod - 2, 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)

Submission status: Time Limit Exceeded

Solution code:
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)
inv = [1] * (total + n)
i = 1
for j in range(1, total + n):
    i = i * j % mod
    fac[j] = i
    inv[j] = pow(i, mod - 2, 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), 2):
    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)

Submission status: Time Limit Exceeded

Solution code:
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)
inv = [1] * (total + n)
i = 1
for j in range(1, total + n):
    i = i * j % mod
    fac[j] = i
    inv[j] = pow(i, mod - 2, mod)



def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod



impossible = 0
for i in range(m + 2, total + 1, 2):
    impossible = (impossible + comb(n, i) * comb(n + (total - i) // 2 - 1, n - 1) % mod) % mod


ret = 0
for i in range(m):
    ret = (ret + comb(i + n - 2, n - 2)) % mod


impossible = (impossible + ret * n) % mod


ret = 0
print((comb(total + n - 1, n - 1) - impossible) % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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):
    @lru_cache(maxsize=None)
    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)
    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 + fn * invs[odd] * invs[n - odd] % MOD * tmp) % MOD
    return ans


n, m = list(map(int, input().split()))
print(solve(n, m))

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

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):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    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):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


factorials = np.array(get_factorials(M * 3 // 2 + N, MOD), dtype=int)
finvs = []
inv = 1
for i in mod_invs(M * 3 // 2 + N, MOD):
    inv = inv * i % MOD
    finvs.append(inv)
finvs = np.array(finvs, dtype=int)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    ret = factorials[n] * finvs[r] % MOD * finvs[n - r] % mod
    ret[n < r] = 0
    return ret


# (1) 合計が M*3 で、奇数の数が M 以下である数列の数
odds = np.arange(M % 2, M + 1, 2)
halves = (M * 3 - odds) // 2

oc1 = ncr(N, odds, MOD)
oc2 = ncr(N - 1, odds, MOD)

# 合計が halfs の数列を 2 倍して、odds 個選んで 1 を足す
c1 = ncr(halves + N - 1, N - 1, MOD) * oc1 % MOD

# (2) max が M*2 より大きく、奇数の数が M 以下である数列の数
# => 合計が M で、1 要素目が 0 より大きい、奇数が M 以下である数列の数 * N
# 1 要素目に M*2 を足せば (2) になる
halves = (M - odds) // 2
# a. 合計が M で奇数が M 以下
c2a = ncr(halves + N - 1, N - 1, MOD) * oc1 % MOD
# c2a = c1
# b. 1 要素目が 0 である数列の数
c2b = ncr(halves + N - 2, N - 2, MOD) * oc2 % MOD

c2 = (c2a - c2b) * N % MOD
print((c1 - c2).sum() % MOD)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

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):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    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):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


factorials = np.array(get_factorials(M * 3 // 2 + N, MOD), dtype=int)
finvs = []
inv = 1
for i in mod_invs(M * 3 // 2 + N, MOD):
    inv = inv * i % MOD
    finvs.append(inv)
finvs = np.array(finvs, dtype=int)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    ret = factorials[n] * finvs[r] % MOD * finvs[n - r] % mod
    ret[n < r] = 0
    return ret


# (1) 合計が M*3 で、奇数の数が M 以下である数列の数
odds = np.arange(M * 3 % 2, M + 1, 2)
halves = (M * 3 - odds) // 2
# 合計が halfs の数列を 2 倍して、odds 個選んで 1 を足す
c1 = ncr(halves + N - 1, N - 1, MOD) * ncr(N, odds, MOD) % MOD

# (2) max が M*2 より大きく、奇数の数が M 以下である数列の数
# => 合計が M で、1 要素目が 0 より大きい、奇数が M 以下である数列の数 * N
# 1 要素目に M*2 を足せば (2) になる
odds = np.arange(M % 2, M + 1, 2)
halves = (M - odds) // 2
# a. 合計が M で奇数が M 以下
c2a = ncr(halves + N - 1, N - 1, MOD) * ncr(N, odds, MOD) % MOD
# b. 1 要素目が 0 である数列の数
c2b = ncr(halves + N - 2, N - 2, MOD) * ncr(N - 1, odds, MOD) % MOD

c2 = (c2a - c2b) * N % MOD
print((c1.sum() - c2.sum()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

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):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    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):
    """
    逆元のリスト 0 から max まで
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


factorials = np.array(get_factorials(M * 3 // 2 + N, MOD), dtype=int)
finvs = []
inv = 1
for i in mod_invs(M * 3 // 2 + N, MOD):
    inv = inv * i % MOD
    finvs.append(inv)
finvs = np.array(finvs)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    ret = factorials[n] * finvs[r] % MOD * finvs[n - r] % mod
    ret[n < r] = 0
    return ret


# (1) 合計が M*3 で、奇数の数が M 以下である数列の数
odds = np.arange(M * 3 % 2, M + 1, 2)
halves = (M * 3 - odds) // 2
# 合計が halfs の数列を 2 倍して、odds 個選んで 1 を足す
c1 = ncr(halves + N - 1, N - 1, MOD) * ncr(N, odds, MOD) % MOD

# (2) max が M*2 より大きく、奇数の数が M 以下である数列の数
# => 合計が M で、1 要素目が 0 より大きい、奇数が M 以下である数列の数 * N
# 1 要素目に M*2 を足せば (2) になる
odds = np.arange(M % 2, M + 1, 2)
halves = (M - odds) // 2
# a. 合計が M で奇数が M 以下
c2a = ncr(halves + N - 1, N - 1, MOD) * ncr(N, odds, MOD) % MOD
# b. 1 要素目が 0 である数列の数
c2b = ncr(halves + N - 2, N - 2, MOD) * ncr(N - 1, odds, MOD) % MOD

c2 = (c2a - c2b) * N
print((c1.sum() - c2.sum()) % MOD)