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: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")


def main():
    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 = np.ones(M * 3 // 2 + N + 1, dtype=int)
    p = 1
    for i, inv in enumerate(mod_invs(M * 3 // 2 + N, MOD)):
        p = p * inv % MOD
        finvs[i] = p

    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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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)

#A
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

#B
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

#C
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) #奇数の数がk個かつ総和が3mとなるパターンの総数(n個のうちk個に1を割り振る→総和が3m-kとなるパターンの総数を求める)
            ans %= mod
    ans -= n*comb(3*m-(2*m+1)+n-1,n-1)
    ans %= mod
    print(ans)

    return

#D
def D():
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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)

#A
def A():
    n = I()
    if n <= 1000000000:
        print(0,0,1,0,0,n)
    else:
        b = math.ceil(n**0.5)
        if b**2 == n:
            print(0,0,b,0,0,n//b)
            return
        x = b
        m = b*x-n
        if m < 0:
            b += 1
            x += 1
            m = b*x-n
        n = m
        for a in range(int(n**0.5)+1)[::-1]:
            if n%a == 0:
                print(0,0,x,n//a,a,b)
                return

    return

#B
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

#C
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

#D
def D():
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

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

FACT=[1]
for i in range(1,4*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(4*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)

Submission status: Accepted

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())
ans = comb(3*m+n-1, n-1)
ans -= n*(m+n-2)*comb(m+n-3, n-2)*pow(n-1, MOD-2, MOD)
for k in range(m+1, n+1):
	if (m-k)%2 == 1:
		continue
	ans -= comb(n, k) * comb((3*m-k)//2+n-1, n-1)
	ans %= MOD
print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stdin, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *
import operator
import math
from fractions import gcd
from random import randint

setrecursionlimit(10**8)

def input():
  return stdin.readline().strip()

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

MAX = 3 * 10**6
MOD = 998244353

fact = [1] * MAX
for i in range(1, MAX):
  fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MAX
invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MAX-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD

def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD if 0 <= k <= n else 0

def H(n, k):
  return comb(n+k-1, k-1)

N, M = reads()

ans =0
for k in range(M%2, M+1, 2):
  d = comb(N, k) * (
    H((3 * M - k) // 2, N)
          - k * H((M-k)//2, N)
          - (N-k) * H((M-2-k)//2, N)
    )
  # print(k, d)
  ans = (ans + d) % MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
frac = [1]*3000000
for i in range(2,3000000):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*3000000
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -3000000-1, -1):
    fraci[i] = fraci[i+1] * (3000000+ i + 1) % mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod


N, M = map(int, input().split())
A = (comb(3*M+N-1, 3*M) - N*(comb(N+M-2, M-1)))%mod
B = 0
if N >= M+1:
    for j in range(M+1, 3*M+1):
        if (3*M-j)%2 == 1:
            continue
        k = (3*M-j)//2
        B = (B+comb(N, j)*comb(k+N-1,k))%mod
        
print((A-B)%mod)

Submission status: Accepted

Solution code:
P = 998244353
fa = [1]
for i in range(1, 3000100):
    fa.append(fa[-1]*i%P)
fainv = [pow(fa[-1], P-2, P)%P]
for i in range(1, 3000100)[::-1]:
    fainv.append(fainv[-1]*i%P)
fainv = fainv[::-1]

def C(a, b):
    return fa[a]*fainv[a-b]*fainv[b]%P

N, M = map(int, input().split())
if N == 2:
    print(M+1)
else:
    ans = C(3*M+N-1, N-1)
    for K in range(2*M+1, 3*M+1):
        ans = (ans - N*C(3*M-K+N-2, N-2)) % P
    for K in range(M):
        if 3*M-K*2 <= N:
            ans = (ans - C(K+N-1, N-1)*C(N, 3*M-K*2)) % P
    print(ans)

Submission status: Runtime Error

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

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

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


A = []
tmp = 0
for i in range(3*M+N+2):
    tmp = (tmp + cmb(N-2+i, N-2)) % mod
    A.append(tmp)

ans = 0
for k in range(min(N, M)+1):
    if (M-k) % 2 != 0: continue
    l = (3*M-k)//2
    a = cmb(N-1+l, N-1) * cmb(N, k)
    b = N * (cmb(N-1, k-1)*A[l-M])
    if l >= M+1:
        b += N * cmb(N-1, k)*A[l-M-1]
    #print(k,a-b)
    ans = (ans + a - b) % mod 
print(ans)

# C = set()
# def calc(d, A):
#     if d == M:
#         t = ""
#         for a in A:
#             t += str(a)
#         C.add(t)
#         return
#     for i in range(N):
#         for j in range(N):
#             if i == j: continue
#             B = A[:]
#             B[i] += 2
#             B[j] += 1
#             calc(d+1, B)
#     return

#calc(0, [0]*N)
#print(len(C))
#print(C)

Submission status: Runtime Error

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

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

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


A = []
tmp = 0
for i in range(M+2):
    tmp = (tmp + cmb(N-2+i, N-2)) % mod
    A.append(tmp)

ans = 0
for k in range(min(N, M)+1):
    if (M-k) % 2 != 0: continue
    l = (3*M-k)//2
    a = cmb(N-1+l, N-1) * cmb(N, k)
    b = N * (cmb(N-1, k-1)*A[l-M])
    if l >= M+1:
        b += N * cmb(N-1, k)*A[l-M-1]
    #print(k,a-b)
    ans = (ans + a - b) % mod 
print(ans)

# C = set()
# def calc(d, A):
#     if d == M:
#         t = ""
#         for a in A:
#             t += str(a)
#         C.add(t)
#         return
#     for i in range(N):
#         for j in range(N):
#             if i == j: continue
#             B = A[:]
#             B[i] += 2
#             B[j] += 1
#             calc(d+1, B)
#     return

#calc(0, [0]*N)
#print(len(C))
#print(C)

Submission status: Runtime Error

Solution code:
o,f,i=998244353,[1],1
while i<o/399:f+=f[-1]*i%o;i+=1
c=lambda n,k:f[n]*pow(f[n-k],o-2,o)*pow(f[k],o-2,o)
n,m=map(int,input().split())
w,u=3*m,n-1
a=c(w+u,u)-n*c(n+m-2,u)
if u>m:
 for i in range(m+1,min(w,n)+1):
  if w-i+1&1:a-=c(n,i)*c((w-i)//2+u,u) 
print(a%o)

Submission status: Runtime Error

Solution code:
o=998244353
f=[1]
for i in range(1,2500100):f.append(f[-1]*i%o)
c=lambda n,k: f[n]*pow(f[n-k],o-2,o)*pow(f[k],o-2,o)%o
n,m=map(int,input().split())
w=3*m
u=n-1
a=c(w+u,u)-n*c(n+m-2,u)
if u>m:
 for i in range(m+1,min(w,n)+1):
  a=(a-c(n,i)*c((w-i)//2+u,u))%o if w-i+1&1
print(a%o)

Submission status: Runtime Error

Solution code:
o=998244353
f=[1]
for i in range(1,2500100):f.append(f[-1]*i%o)
def c(n,k):return f[n]*pow(f[n-k],o-2,o)*pow(f[k],o-2,o)%o
n,m=map(int,input().split())
w=3*m
u=n-1
a=c(w+u,u)-n*c(n+m-2,u)
if u>m:
 for i in range(m+1,min(w,n)+1):
  if w-i+1&amp;1:a=(a-c(n,i)*c((w-i)//2+u,u))%o
print(a%o)

Submission status: Runtime Error

Solution code:
o=998244353
f=[1]
for i in range(1,2500100):f.append(f[-1]*i%o)
def c(n,k):return f[n]*pow(f[n-k],o-2,o)*pow(f[k],o-2,o)%o
n,m=map(int,input().split())
w=3*m
u=n-1
a=c(w+u,u)-n*c(n+m-2,u)
if u&gt;m:
 for i in range(m+1,min(w,n)+1):
  if w-i+1&amp;1:a=(a-c(n,i)*c((w-i)//2+u,u))%o
print(a%o)

Submission status: Runtime Error

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

import numpy as np

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

def cumprod_mod(arr):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    arr = arr.ravel()[:L]
    return arr

U = 2*10**6 + 100
x = np.arange(U,dtype=np.int64)
x[0] = 1
fact = cumprod_mod(x)

x = np.arange(U,0,-1,dtype=np.int64)
x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod_mod(x)[::-1]

def comb(n,k):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

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

# 奇数がM+1個以上あるものを除く
odd_cnt = np.arange(M+2,3*M+1,2)
S = (3*M - odd_cnt)//2
bl = (odd_cnt <= N)&(S>=0)
odd_cnt = odd_cnt[bl]
S = S[bl]
arr = fact[N] * fact_inv[odd_cnt] % MOD * fact_inv[N-odd_cnt] % MOD
# SをN個で作る -> S+N-1 C N-1
arr *= fact[S+N-1] * fact_inv[N-1] % MOD * fact_inv[S] % MOD
arr %= MOD
z = arr.sum() % MOD

answer = x-y-z
answer %= MOD
print(answer)

Submission status: Runtime Error

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 = 10**6
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

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

Submission status: Runtime Error

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

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

FACT=[1]
for i in range(1,2*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


ANS=Combi(M*3+N-1,N-1)

for i in range(M*2+1,M*3+1):
    k=M*3-i
    ANS=(ANS-N*Combi(k+(N-1)-1,N-2))%mod


for i in range(M+1,N+1):
    if (M*3-i)%2==1:
        continue
    k=(M*3-i)//2
    ANS=(ANS-Combi(N,i)*Combi(k+N-1,N-1))%mod

print(ANS)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 7 + 10)


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


@lru_cache(maxsize=None)
def pattern(t, k, x):
    # print('', t, k, x)
    if k * x < t:
        # print(t, k, x, 0)
        return 0
    if k * x == t or t == 0 or k == 1:
        # print(t, k, x, 1)
        return 1
    ans = pattern(t, k, x - 1)
    # print(f'  ({t} {k} {x} 0 {ans})')
    for i in range(1, t // x + 1):
        ans = (ans + pattern(t - x * i, k - i, x - 1) * facts[k] * invs[i] * invs[k - i]) % MOD
        # print(f'  ({t} {k} {x} {i} {ans})')

    # print(t, k, x, ans)
    return ans


MOD = 998244353
n, m = list(map(int, input().split()))
facts, invs = prepare(n, MOD)
print(pattern(3 * m, n, 2 * m))

Submission status: Runtime Error

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

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

U = 2 * 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: Runtime Error

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

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

U = 2 * 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 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: Runtime Error

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

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

U = 2 * 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):
    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 以上
answer %= MOD

print(answer)

Submission status: Runtime Error

Solution code:
P = 998244353
fa = [1]
for i in range(1, 1000100):
    fa.append(fa[-1]*i%P)

def C(a, b):
    return fa[a]*pow(fa[a-b]*fa[b], P-2, P)%P

N, M = map(int, input().split())
if N == 2:
    print(M+1)
else:
    ans = C(3*M+N-1, N-1)
    for K in range(2*M+1, 3*M+1):
        ans = (ans - N*C(3*M-K+N-2, N-2)) % P
    for K in range(M):
        if 3*M-K*2 <= N:
            ans = (ans - C(K+N-1, N-1)*C(N, 3*M-K*2)) % P
    print(ans)

Submission status: Runtime Error

Solution code:
N = input(N)
M = int(input())
print(2 ** M)