Problem:


Score : 600 points

Problem Statement

We have a grid with A horizontal rows and B vertical columns, with the squares painted white. On this grid, we will repeatedly apply the following operation:

Assume that the grid currently has a horizontal rows and b vertical columns. Choose "vertical" or "horizontal".

If we choose "vertical", insert one row at the top of the grid, resulting in an (a+1) \times b grid.

If we choose "horizontal", insert one column at the right end of the grid, resulting in an a \times (b+1) grid.

Then, paint one of the added squares black, and the other squares white.

Assume the grid eventually has C horizontal rows and D vertical columns. Find the number of ways in which the squares can be painted in the end, modulo 998244353.

Constraints

1 \leq A \leq C \leq 3000

1 \leq B \leq D \leq 3000

A, B, C, and D are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of ways in which the squares can be painted in the end, modulo 998244353.

Sample Input 1

1 1 2 2

Sample Output 1

3

Any two of the three squares other than the bottom-left square can be painted black.

Sample Input 2

2 1 3 4

Sample Output 2

65

Sample Input 3

31 41 59 265

Sample Output 3

387222020



Sample input:
1 1 2 2


Sample output:
3

Submission status: Runtime Error

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

sys.setrecursionlimit(3000)

A, B, C, D = nn()

memo_f = {}
memo_g = {}
mod = 998244353

def f(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)
    if (x, y) in memo_f:
        return memo_f[(x, y)]

    s = (f(x-1, y) * y) % mod
    t = (f(x, y-1) * x) % mod
    u = (g(x-1, y) * (y-1)) % mod
    memo_f[(x, y)] = (s + t - u) % mod
    return (s + t - u) % mod

def g(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)

    s = (f(x, y-1) * x) % mod
    t = (g(x-1, y) * (y-1)) % mod
    return (s + t) % mod

print(f(C, D))

Submission status: Runtime Error

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

A, B, C, D = nn()

memo_f = {}
memo_g = {}
mod = 998244353

def f(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)
    if (x, y) in memo_f:
        return memo_f[(x, y)]

    s = (f(x-1, y) * y) % mod
    t = (f(x, y-1) * x) % mod
    u = (g(x-1, y) * (y-1)) % mod
    memo_f[(x, y)] = (s + t - u) % mod
    return (s + t - u) % mod

def g(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)

    s = (f(x, y-1) * x) % mod
    t = (g(x-1, y) * (y-1)) % mod
    return (s + t) % mod

print(f(C, D))

Submission status: Runtime Error

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

mod = 998244353


NN = 10**4 # 使うデータによって変える

inv = [0]
for i in range(1, NN):
    inv.append(pow(i, mod-2, mod))

def main():
    A, B, C, D = map(int, input().split())
    dp = [[0]*(D+1) for _ in range(C+1)]
    dp2 = [[0]*(D+1) for _ in range(C+1)]


    for w in range(B-1, D+1):
        dp[A][w] = 0
        dp2[A][w] = pow(A, (D-B), mod)


    for c in range(A+1, C+1):
        t = pow(c*inv[c-1] % mod, D-B-1, mod)
        kakeru = (c-1)*inv[c] % mod
        dp[c][B] = pow(B,c-A,mod) * pow(c, D-B, mod) % mod
        dp2[c][B] = dp[c][B]
        for d in range(B+1, D+1):
            dp[c][d] = (dp2[c-1][d-1] + dp[c-1][d]*d % mod ) * t % mod
            t = t * kakeru % mod
            dp2[c][d] = (dp2[c][d-1] + dp[c][d]) % mod

    print(dp2[C][D])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

A, B, C, D = nn()

memo_f = {}
memo_g = {}
mod = 998244353

def f(x, y):
    if x == A: return (A ** (y - B)) % mod
    if y == B: return (B ** (x - A)) % mod
    if (x, y) in memo_f:
        return memo_f[(x, y)]

    s = (f(x-1, y) * y) % mod
    t = (f(x, y-1) * x) % mod
    u = (g(x-1, y) * (y-1)) % mod
    memo_f[(x, y)] = (s + t - u) % mod
    return (s + t - u) % mod

def g(x, y):
    if x == A: return (A ** (y - B)) % mod
    if y == B: return (B ** (x - A)) % mod

    s = (f(x, y-1) * x) % mod
    t = (g(x-1, y) * (y-1)) % mod
    return (s + t) % mod

print(f(C, D))
#print(memo_f)

Submission status: Runtime Error

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
a,b,c,d=map(int,input().split())
mod=998244353


dp=[[0]*3005 for _ in range(3005)]
for i in range(a+1):
    for j in range(b+1):
        dp[i][j]=1
#print(dp)

for i in range(3003-a):
    dp[a][b+i+1]=((dp[a][b+i])*a)%mod
for j in range(3003-b):
    dp[a+1+j][b]=((dp[a+j][b]*b))%mod

    
for i in range(3003-a):
    for j in range(3003-b):
        dp[i+1][j+1]=(dp[i][j+1]*(j+1))%mod+(dp[i+1][j]*(i+1))%mod-(a*b)%mod
        
print(dp[c-a][d-a]%mod)

Submission status: Runtime Error

Solution code:
a,b,c,d=map(int,input().split())

n_list=[0 for j in range(d)]
m_list=[0 for i in range(c)]

for i in range(a-1,c) :
  m_list[i]=b**(i-a+1)

for i in range(b-1,d) :
  n_list[i]=a**(i-b+1)


import copy

for i in range(b,d) :
  m_list1=copy.copy(m_list)
  m_list[b]=n_list[i]
  for j in range(a,c) :
    
    m_list[j]=m_list1[j]*(j+1)+m_list[j-1]*(i+1)-m_list1[j-1]*j*i




print(m_list[-1]%998244353)

Submission status: Runtime Error

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

mod = 998244353

A, B, C, D = map(int, input().split())
dp = [[0]*(D+1) for _ in range(C+1)]
dp2 = [[0]*(D+1) for _ in range(C+1)]


for w in range(B-1, D+1):
    dp[A][w] = 0
    dp2[A][w] = pow(A, (D-B), mod)

for c in range(A+1, C+1):
    invc = pow(c-1, mod-2, mod)
    t = pow(c*invc, D-B-1, mod)
    kakeru = pow(invc*c, mod-2, mod)
    dp[c][B] = pow(B,c-A,mod) * pow(c, D-B, mod) % mod
    dp2[c][B] = dp[c][B]
    for d in range(B+1, D+1):
        dp[c][d] = (dp2[c-1][d-1] + dp[c-1][d]*d ) * t % mod
        t = t * kakeru % mod
        dp2[c][d] = (dp2[c][d-1] + dp[c][d]) % mod

print(dp2[C][D])

Submission status: Runtime Error

Solution code:
A,B,C,D = map(int, input().split())
 
x = C-A + 1
y = D-B + 1
dp = [[0 for j in range(y)] for i in range(x)]
dp[0][0] = 1
for i in range(x):
  for j in range(y):
    if i==0 and j==0:
      pass
    elif i==0:
      dp[i][j] = (dp[i][j-1]*A)
    elif  j==0:
      dp[i][j] = (dp[i-1][j]*B)
    else:
      dp[i][j] = (dp[i][j-1]*(A+i) + dp[i-1][j])
    dp[i][j] %= 998244353
print(dp[x][y])

Submission status: Runtime Error

Solution code:
#wrong sample.
a,b,c,d=map(int,input().split())
mod=998244353
f=[1]
for i in range(10000):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
dp=[(d+1)*[0]for _ in range(c+1)]
dp[a][b]=1
def dfs(x,y):
  if dp[x][y]!=0:return dp[x][y]
  if x!=a and y!=b:
    ans=(dfs(x-1,y-1)*comb(x+y-1,2))%mod
    if (x-a)+(y-b)-1>=2:
      ans=(ans+comb(x-a+y-b-1,2))%mod
  elif x!=a:
    ans=(dfs(x-1,y)*y)%mod
  elif y!=b:
    ans=(dfs(x,y-1)*x)%mod
  else:
    ans=1
  dp[x][y]=ans
  return ans
print(dfs(c,d))
#for i in dp:print(i)

Submission status: Runtime Error

Solution code:
a,b,c,d = list(map(int,input().split()))

dp = [[-1]*3001 for i in range(3001)]

for i in range(a+1):
	for j in range(b+1):
		dp[i][j] = 1

mod = 998244353

def num(x,y):
	if x == a and y == b:
		return 0
	elif x < a or y < b:
		return 0
	return solv(x,y)

def solv(x,y):
	if x < a or y < b:
		return 0
	if dp[x][y] >= 0:
		return dp[x][y]
	x_ = (solv(x-1,y) * y) % mod
	y_ = (solv(x,y-1) * x) % mod

	ref = (x_ + y_)%mod
	if solv(x-1,y) == 0 or solv(x,y-1) == 0:
		dp[x][y] = ref
		return ref
	ref %= mod
	ref += mod
	ref -= ((((x-1)*(y-1)) % mod) * solv(x-1,y-1)) % mod
	
	ref %= mod
	dp[x][y] = ref
	return ref

print(solv(c,d))

Submission status: Runtime Error

Solution code:
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d-b+1) for i in range(c-a+1)]
if a == c and b == d:
    print(1)
elif a == c:
    print(a)
elif b == d:
    print(b):
else:
    for i in range(c-a):
        p = 0
        for j in range(d-b+1):
            if i == j == 0:
                dp[i][j] = 1
            dp[i+1][j] = (p + dp[i][j]*(b+j))%mod

            p += dp[i][j]
            p %= mod
            p *= a+i
            p %= mod

    ans = 0
    for d in dp[-1]:
        ans *= c
        ans %= mod
        ans += d
        ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
a,b,c,d = map(in        list.append(int(a[i]))
    print(list)
    i = 1
    while True:
        b = x+i
        c = x-i
        if list.__contains__(b) and list.__contains__(c):
            i = i+1
        else:
            list1.append(b)
            list1.append(c)
            if(b>n and c<n):
                print(b)
            else:
                print

Submission status: Runtime Error

Solution code:
A, B, C, D = map(int,input().split())

d={}
d[(A,B)]=1
for i in range(A+1,C+1):
  d[(i,B)] *= B*d[(i-1,B)] % 998244353
for j in range(B+1,D+1):
  d[(A,j)] *= A*d[(A,j-1)] % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=(j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]) % 998244353
    
print(d[(C,D)] % 998244353)

Submission status: Runtime Error

Solution code:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
  
a,b,c,d=map(int,input().split())

ans=cmb(c*d-a*b,c+d-a-b)

ans=ans%998244353

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    mod = 998244353
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in [0]*(c+1)]
    dp[a][b] = 1
    for i in range(a+b+1, c+d+1):
        for p in range(c, a-1, -1):
            q = i-p
            if q > d:
                break
            dp[p][q] = (q*dp[p-1][q]+p*dp[p][q-1] -
                        (p-1)*(q-1)*dp[p-1][q-1]) % mod
    print(dp[c][d])


main()

Submission status: Runtime Error

Solution code:
A,B,C,D=map(int,input().split())
if x==A or x==B:
  if x==B:
    A=(A+1)*B
   elif x==A:
    B=A*(B+1)
   else:

Submission status: Runtime Error

Solution code:
M = 1001;  
MOD = 998244353;  
  
dp = [[-1]* M ] * M 
 
def main(idx, diff, N, M, K) : 
    if (idx > N) :  
        if (diff == K) : 
            return 1 
        return 0
    
    if (dp[idx][ diff] != -1) : 
        return dp[idx];  
 
    ans = main(idx + 1, diff, N, M, K);  
   
    ans += (M - 1) * solve(idx + 1, diff + 1, N, M, K);  
  
    dp[idx][ diff] = ans % MOD;  
      
    return dp[idx][ diff] 

if __name__ == "__main__" :  
  
    N = 3
    M = 3
    K = 0 

    print(M * solve(2, 0, N, M, K))

Submission status: Runtime Error

Solution code:
A,B,C,D = map(int, input().split())

x = C-A + 1
y = D-B + 1
dp = [[0 for j in y] for i in x]
dp[0][0] = 1
for i in range(x):
  for j in range(y):
    if i==0 and j==0:
      continue
    if i==0:
      dp[i][j] = dp[i][j-1]*A
      continue
    if  j==0:
      dp[i][j] = dp[i-1][j]*B
      continue
    dp[i][j] = (dp[i][j-1]*(A+i) + dp[i-1][j]*(B+j) + (A+B+i+j-2))//2
print(dp[x-1][y-1]%998244353)