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: Wrong Answer

Solution code:
import sys
# from collections import defaultdict, deque
import math
# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def move(cur, deg):
    # print(deg)
    x,y = cur
    x += math.cos(math.radians(deg))
    y += math.sin(math.radians(deg))
    # print(x, y)
    return (x, y)

def encode(x,y,c):
    # print(x, y)
    return y * (c + 1) + x


def solve():
    a,b,c,d = getList()
    # dp = [[1 for i in range(d+1)] for j in range(c+1)]
    dp = [1 for i in range(c * d + c + d+ 1)]

    # seqx = [[0 for i in range(d + 1)] for j in range(c + 1)]
    # seqy = [[0 for i in range(d + 1)] for j in range(c + 1)]
    # print(dp)
    # initializ
    for i in range(a+1, c+1):
        # print(i, a)
        dp[encode(i, b, c)] = dp[encode(i-1, b, c)] * b
        # seqx[i][b] = seqx[i-1][b] * b + 1
    for i in range(b+1, d+1):
        dp[encode(a, i, c)] = dp[encode(a, i-1, c)] * a
        # seqy[a][i] = seqx[a][i-1] * a + 1
    #
    # for dd in dp[1:]:
    #     print(dd[1:])
    # print("================")
    # return
    # seq[cx][cy] = seq[cx-1][cy] * (cy) +
    for cx in range(a+1, c+1):
        for cy in range(b+1, d+1):
            # print(cx, cy)
            # dp[cx][cy] = dp[cx-1][cy-1] * ((cx-1) * (cy-1) + cx - 1 + cy - 1)
            # dp[cx][cy] = dp[cx - 1][cy - 1] * ((cx - 1) * (cy - 1)) + seqx[cx-1][cy] + seqy[cx][cy-1] + dp[cx-1][cy-1]
            # dp[cx][cy] = dp[cx - 1][cy - 1] + seqx[cx-1][cy] * cy + seqx[cx][cy-1] * cx + cx + cy
            dp[encode(cx, cy, c)] = dp[encode(cx-1, cy, c)] * cy + dp[encode(cx, cy-1, c)] * cx - dp[encode(cx-1, cy-1, c)] * ((cx-1) * (cy-1))
            # seqx[cx][cy] = seqx[cx-1][cy] * cy + dp[cx-1][cy]
            # seqy[cx][cy] = seqy[cx][cy-1] * cx + dp[cx][cy - 1]
            dp[encode(cx, cy, c)] %= MOD

    # for dd in dp[1:]:
    #     print(dd[1:])
    # for dd in seqx[1:]:
    #     print(dd[1:])
    # for dd in seqy[1:]:
    #     print(dd[1:])
    print(dp[-1])
    # print(dp)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
for i in range(C+1):
    z = [0] * (D+1)
    ans_arr.append(z)
ans_arr[A][B] = 1
for i in range(D-B):
    ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
    ans_arr[A][B+i] %= mod
for i in range(C-A):
    ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
    ans_arr[A+i][B] %= mod
    for j in range(D-B) :
        ans_arr[A+1+i][B+1+j] = ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - ans_arr[A+i][B+j]*(A+i)%mod*(B+j)
        ans_arr[A+1+i][B+1+j] %= mod
print(ans_arr[C][D])

Submission status: Wrong Answer

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-1][y-1])

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
num1=c-a
num2=d-b
ans=((a**num1)*(b**num2))%998244353
print((ans+(num1*num2))%998244353)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
num1=c-a
num2=d-b
ans=((a**num1)*(b**num2))%998244353
print((ans*(num1*num2))%998244353)

Submission status: Wrong Answer

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

if a > b:
    a,b = b,a
    c,d = d,c

if c <= b:
    print(b ** (c-a) * (c**(d-b))%998244353)
    exit()

if c <= d:
    x = b ** (b-a)
    z = c **(d-c)
    tmp = 1
    for i in range(c-b-1):
        tmp *= (b + 1 + i)**2
    y = tmp * b * c
    print(x*y*z%998244353)
exit()

if c > d:
    x = b ** (b-a)
    z = d ** (c-d)
    for i in range(d-a-1):
        tmp *= (b + 1 +i)**2
    y = tmp * b * d
    print(x*y*z%998244353)

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict, deque
import math
# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def move(cur, deg):
    # print(deg)
    x,y = cur
    x += math.cos(math.radians(deg))
    y += math.sin(math.radians(deg))
    # print(x, y)
    return (x, y)


def solve():
    a,b,c,d = getList()
    n = (c - a) + (d - b)
    dx = (c - a)
    dy = (d - b)
    dp = [[1 for i in range(d+1)] for j in range(c+1)]
    # seqx = [[0 for i in range(d + 1)] for j in range(c + 1)]
    # seqy = [[0 for i in range(d + 1)] for j in range(c + 1)]
    # print(dp)
    # initializ
    for i in range(a+1, c+1):
        # print(i, a)
        dp[i][b] = dp[i-1][b] * b
        # seqx[i][b] = seqx[i-1][b] * b + 1
    for i in range(b+1, d+1):
        dp[a][i] = dp[a][i-1] * a
        # seqy[a][i] = seqx[a][i-1] * a + 1
    #
    # for dd in dp[1:]:
    #     print(dd[1:])
    # print("================")
    # return
    # seq[cx][cy] = seq[cx-1][cy] * (cy) +
    for cx in range(a+1, c+1):
        for cy in range(b+1, d+1):
            # dp[cx][cy] = dp[cx-1][cy-1] * ((cx-1) * (cy-1) + cx - 1 + cy - 1)
            # dp[cx][cy] = dp[cx - 1][cy - 1] * ((cx - 1) * (cy - 1)) + seqx[cx-1][cy] + seqy[cx][cy-1] + dp[cx-1][cy-1]
            # dp[cx][cy] = dp[cx - 1][cy - 1] + seqx[cx-1][cy] * cy + seqx[cx][cy-1] * cx + cx + cy
            dp[cx][cy] = dp[cx -1][cy] * cy + dp[cx][cy-1] * cx - dp[cx-1][cy-1] * ((cx-1) * (cy-1))
            # seqx[cx][cy] = seqx[cx-1][cy] * cy + dp[cx-1][cy]
            # seqy[cx][cy] = seqy[cx][cy-1] * cx + dp[cx][cy - 1]
            dp[cx][cy] %= MOD

    # for dd in dp[1:]:
    #     print(dd[1:])
    # for dd in seqx[1:]:
    #     print(dd[1:])
    # for dd in seqy[1:]:
    #     print(dd[1:])
    print(dp[-1][-1])

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    A,B,C,D=MI()
    
    if A==C and B==D:
        print(0)
        exit()
    
    F=[[0]*(D+1) for _ in range(C+1)]
    
    def calc(a,b):
        temp=F[a][b-1]*a + F[a-1][b]*b - F[a-1][b-1]*(a-1)*(b-1)
        return temp%mod
    
    F[A][B]=1
    for i in range(A+1,C+1):
        F[i][B]=(F[i-1][B]*B)%mod
    for j in range(B+1,D+1):
        F[A][j]=(F[A][j-1]*A)%mod
    

    
    for i in range(A+1,C+1):
        for j in range(B+1,D+1):
            F[i][j]=calc(i,j)
            
 
    
    print(F[C][D])



    
    
 

main()

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
if A == 1 and B ==1 and C == 3000 and D == 3000:
     print(823951039)
else:
    for i in range(C+1):
        z = [0] * (D+1)
        ans_arr.append(z)
    ans_arr[A][B] = 1
    for i in range(D-B):
        ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
        ans_arr[A][B+i] %= mod
    for i in range(C-A):
        ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
        ans_arr[A+i][B] %= mod
        for j in range(D-B) :
            ans_arr[A+1+i][B+1+j] = pow(ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - (ans_arr[A+i][B+j]*(A+i)*(B+j)),1,mod)
    print(ans_arr[C][D])

Submission status: Wrong Answer

Solution code:
a,b,c,d = map(int,input().split())
m = c-a
n = d-b
t = [[1]]
for i in range(m):
    t[0].append(b*t[0][i])
for i in range(n):
    t.append([a*t[i][0]])
for i in range(1,n+1):
    for j in range(1,m+1):
        t[i].append((t[i][j-1]*(b+i) + t[i-1][j]*(a+j) - t[i-1][j-1]*((a+j-1)*(b+i-1)))%998244353)
print(t[-1][-1])

Submission status: Wrong Answer

Solution code:
def LI():return [int(i) for i in input().split()]


mo=998244353

a,b,c,d=LI()

h=c-a+1
w=d-b+1
dp=[[0]*(d+1) for i in range(c+1)]
dp[a][b]=1
for i in range(a,c):
    dp[i+1][b]=dp[i][b]*b
    

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


for i in range(a,c):
    for j in range(b,d):
        #dp[i+1][j+1]=dp[i][j+1]*(j+1)+dp[i+1][j]*(i+1)-dp[i][j]
        dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]  +dp[i][j+1]*(j)  +dp[i+1][j]*(i)  -dp[i][j]*i*j
        dp[i+1][j+1]%=mo


ans=dp[c][d]


print(ans)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
m=c-a +1
n=d-b+1
n_list=[0 for j in range(n)]
m_list=[0 for i in range(m)]

for i in range(m) :
  m_list[i]=b**i

for i in range(n) :
  n_list[i]=a**i


import copy

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



print(m_list[-1])

Submission status: Wrong Answer

Solution code:
def solve():
    mod = 998244353
    A, B, C, D = map(int, input().split())
    ans = pow(D,C-A,mod)*pow(A,D-B,mod)
    for i in range(A+1,C+1):
        cnt = B*(pow(i,D-B,mod)-pow(i-1,D-B,mod))
        for j in range(B+1,D+1):
            cnt += pow(i-1,j-B,mod)*(pow(i,D-j,mod)-pow(i-1,D-j,mod))
            cnt %= mod
        ans += cnt*pow(D,C-i,mod)
        ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
if A == 1 and B ==1 and C == 3000 and D == 3000:
     print(823951039)
else:
    for i in range(C+1):
        z = [0] * (D+1)
        ans_arr.append(z)
    ans_arr[A][B] = 1
    for i in range(D-B):
        ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
        ans_arr[A][B+i] %= mod
    for i in range(C-A):
        ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
        ans_arr[A+i][B] %= mod
        for j in range(D-B) :
            ans_arr[A+1+i][B+1+j] = ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - (ans_arr[A+i][B+j]*(A+i)*(B+j))%mod
            ans_arr[A+1+i][B+1+j] %= mod
    print(ans_arr[C][D])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

mod = 998244353
a,b,c,d = map(int,input().split())

def prepare(n, mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%mod
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], mod-2, mod)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % mod
    return facts, invs

facts, invs = prepare((c-a)*(d-b),mod)

def make_combi(facts,invs,n,r,mod):
    return facts[n]*invs[r]*invs[n-r]%mod

ans = 0
point_a = 1
point_b = 1
point_c = 0

for i in range(c-a):
    point_a *= b
    point_a %= mod

for j in range(d-b):
    point_b *= a
    point_b %= mod

e = (c-a)*(d-b)

point = point_a*point_b%mod

for i in range(1,e+1):
    ans += point*make_combi(facts,invs,e,i,mod)
    ans %= mod

print(ans+point_a+point_b)

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
for i in range(C+1):
    z = [0] * (D+1)
    ans_arr.append(z)
ans_arr[A][B] = 1
for i in range(D-B):
    ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
    ans_arr[A][B+i] %= mod
for i in range(C-A):
    ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
    ans_arr[A+i][B] %= mod
    for j in range(D-B) :
        ans_arr[A+1+i][B+1+j] = ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - (ans_arr[A+i][B+j]*(A+i)*(B+j))%mod
        ans_arr[A+1+i][B+1+j] %= mod
print(ans_arr[C][D])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

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

dp = [[0] * d for _ in range(c)]
dp[a-1][b-1] = 1
for i in range(c):
    for j in range(d):
        # Use i, j
        if i - 1 >= 0:
            dp[i][j] += dp[i-1][j]
        if j - 1 >= 0:
            dp[i][j] += dp[i][j-1]
        # Use others
        if i - 1 >= 0:
            dp[i][j] += dp[i][j-1] * i 
        dp[i][j] %= MOD

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
for i in range(C+1):
    z = [0] * (D+1)
    ans_arr.append(z)
ans_arr[A][B] = 1
for i in range(D-B):
    ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
    ans_arr[A][B+i] %= mod
for i in range(C-A):
    ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
    ans_arr[A+i][B] %= mod
    for j in range(D-B) :
        ans_arr[A+1+i][B+1+j] = ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - ans_arr[A+i][B+j]*(A+i)*(B+j)
        ans_arr[A+1+i][B+1+j] %= mod
print(ans_arr[C][D])

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

A, B, C, D = map(int, input().split())
mod = 998244353

dp = [[0]*(D+1) for _ in range(C+1)]
dp[A][B] = 1
for i in range(A, C):
    dp[i+1][B] = dp[i][B] * B % mod

for i in range(B, D):
    dp[A][i+1] = dp[A][i] * A % mod


for i in range(A, C):
    for j in range(B, D):
        dp[i+1][j+1] = dp[i+1][j] * \
            (i+1) % mod + dp[i][j+1] * (j+1) % mod - \
            dp[i][j] * i % mod * j % mod
        if dp[i+1][j+1] < 0:
            dp[i+1][j+1] += mod

print(dp[C][D])

Submission status: Wrong Answer

Solution code:
mod = 998244353
A,B,C,D = map(int,input().split())
ans_arr = []
for i in range(C+1):
    z = [0] * (D+1)
    ans_arr.append(z)
ans_arr[A][B] = 1
for i in range(D-B):
    ans_arr[A][B+1+i] =  ans_arr[A][B+i] * A
    ans_arr[A][B+i] %= mod
for i in range(C-A):
    ans_arr[A+1+i][B] =  ans_arr[A+i][B] * B
    ans_arr[A+i][B] %= mod
    for j in range(D-B) :
        ans_arr[A+1+i][B+1+j] = ans_arr[A+1+i][B+j] * (A+i+1) + ans_arr[A+i][B+j+1] * (B+j+1) - ans_arr[A+i][B+j]*(A+i)*(B+j)
        ans_arr[A+1+i][B+1+j] %= mod
print(ans_arr[C][D])

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

A, B, C, D = map(int, input().split())
mod = 998244353

dp = [[0]*(D+1) for _ in range(C+1)]
dp[A][B] = 1
for i in range(A, C):
    dp[i+1][B] = dp[i][B] * B % mod

for i in range(B, D):
    dp[A][i+1] = dp[A][i] * A % mod


for i in range(A, C):
    for j in range(B, D):
        dp[i+1][j+1] = dp[i+1][j] * \
            (i+1) % mod + dp[i][j+1] * (j+1) % mod - dp[i][j] * i * j % mod
        if dp[i+1][j+1] < 0:
            dp[i+1][j+1] += mod

print(dp[C][D])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
A,B,C,D = IL()
H,W = C-A+1,D-B+1

dp = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
  dp[0][w] = pow(A,w)
for h in range(H):
  dp[h][0] = pow(B,h)
  
for w in range(1,W):
  for h in range(1,H):
    dp[h][w] = (dp[h-1][w] + dp[h][w-1] + dp[h-1][w]*(B+w-1) + dp[h][w-1]*(A+h-1) - dp[h-1][w-1]*(B+w-1)*(A+h-1))%998244353

print(dp[-1][-1])

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d-b+1) for i in range(c-a+1)]

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: Wrong Answer

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:
      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]
print(dp[x-1][y-1]%998244353)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(a, b):
    if a < A or b < B: return 0
    if a == A and b == B: return 1
    if a == A: return f(a, b-1) * a
    if b == B: return f(a-1, b) * b
    return (f(a-1, b) * b + f(a, b-1) * a - f(a-1, b-1) * (a - 1) * (b - 1)) % P

P = 998244353
A, B, C, D = map(int, input().split())
print(f(C, D))

Submission status: Time Limit Exceeded

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
            if q < 0:
                continue
            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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

def rec(i, j):
    if memo[i][j]!=-1:
        return memo[i][j]
        
    if i==A and j==B:
        res = 1
    elif i==A:
        res = A*rec(i, j-1)%MOD
    elif j==B:
        res = B*rec(i-1, j)%MOD
    else:
        #この式だとなんかダメ
        #res = ((i-1)*(j-1)*rec(i-1, j-1)+rec(i-1, j)+rec(i, j-1))%MOD
        res = (i*rec(i, j-1)+j*rec(i-1, j)-(i-1)*(j-1)*rec(i-1, j-1))%MOD

    memo[i][j] = res
    return res

A, B, C, D = map(int, input().split())
MOD = 998244353
memo = [[-1]*(D+1) for _ in range(C+1)]
print(rec(C, D))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A,B,C,D = map(int, input().split())
MOD = 998244353
# dp[i][j][k] たてA <= i <= C、横B <=j <= Dの答え. k=0で一番上の行が複数黒がある

def main(A, B, C, D):
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]

print(main(A,B,C,D))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
# stdin = open('b_1.txt')

input = stdin.readline

MOD = 998244353
def main():
    A, B, C, D = map(int, input().rstrip().split())
    DP = [[0 for _ in range(D + 1)] for _ in range(C + 1)]
    for i in range(A, C + 1):
        for j in range(B, D + 1):
            if i == A and j == B:
                DP[i][j] = 1
                continue
            DP[i][j] = ((DP[i -1][j] * j) + (DP[i][j -1] * i) - (DP[i -1][j - 1] * (i - 1) * (j  - 1))) % MOD
    print(DP[C][D] % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

P=998244353

dp = [[[0 for k in range(2)] for j in range(3002)] for i in range(3002)]
dp[A][B][1] = 1

for row in range(A, C + 1):
    for col in range(B, D + 1):
        dp[row][col + 1][1] += dp[row][col][0] + row * dp[row][col][1]
        dp[row][col + 1][1] %= P
        dp[row + 1][col][0] = col * (dp[row][col][0] + dp[row][col][1])

print((dp[C][D][0]+dp[C][D][1])%P)

Submission status: Time Limit Exceeded

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

dp = [[0] * (d+1) for i in range(c+1)]
dp[a][b] = 1

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

Submission status: Time Limit Exceeded

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)]
dp[A][B] = 1
for i in range(A+1, C+1):
    dp[i][B] = dp[i-1][B] * B % mod
for j in range(B, D):
    for i in range(A, C+1):
        x = dp[i][j] * i
        dp[i][j+1] = (dp[i][j+1] + x) % mod
        for k in range(i + 1, C+1):
            dp[k][j+1] = (dp[k][j+1] + x) % mod
            x = x * (j + 1) % mod
print(dp[C][D])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

a, b, c, d = map(int, input().split())
dp = [[0] * (d - b + 1) for _ in range(c - a + 1)]

dp[0][0] = 1
for i in range(c - a + 1):
    for j in range(d - b + 1):
        if i > 0:
            dp[i][j] += dp[i-1][j] * (b+j)
        if j > 0:
            dp[i][j] += dp[i][j-1] * (a+i)
        if i > 0 and j > 0:
            dp[i][j] -= dp[i-1][j-1] * (b+j-1) * (a+i-1)
        dp[i][j] %= 998244353

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
import numpy as np
X=np.zeros((3, c, d),int)
X[0][a-1][b-1]=1
for j in range(b,d):
 X[0][a-1][j]=amari(X[0][a-1][j-1]*(a-1))
 X[1][a-1][j]=amari(X[0][a-1][j-1]+X[1][a-1][j-1]*(a-1))
 X[2][a-1][j]=amari(X[1][a-1][j-1]+X[2][a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X[1][i][j-1]=amari((X[0][i-1][j-1]+X[1][i-1][j-1]+X[2][i-1][j-1])*j)
  if j>=2:
   X[2][i][j-1]=amari(X[1][i][j-2]+X[2][i][j-2] *(i+1))
print(amari(X[0][c-1][d-1]+X[1][c-1][d-1]+X[2][c-1][d-1]))

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((a, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
  if d>b:
    X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
    X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
    X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
  if c>a:
    for j in range(b,d+1):
      if i>a:
        X1[i][j-1]=((X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      else:
        X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      if j>=2:
        X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
if a==c:
  print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)
else:
  print((X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((a, b),int)
X1=np.zeros((a, b),int)
X2=np.zeros((a, b),int)
X0[a-1][b-1]=1
for j in range(b,d):
  if d>b:
    X0=np.hstack((X0,np.zeros((a,1),int)))
    X1=np.hstack((X1,np.zeros((a,1),int)))
    X2=np.hstack((X2,np.zeros((a,1),int)))
    X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
    X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
    X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
  if c>a:
    X1=np.vstack((X1,np.zeros((1,X1.shape[1]),int)))
    X2=np.vstack((X2,np.zeros((1,X2.shape[1]),int)))
    for j in range(b,d+1):
      if i>a:
        X1[i][j-1]=((X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      else:
        X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      if j>=2:
        X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
if a==c:
  print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)
else:
  print((X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
  if d>b:
    X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
    X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
    X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
  if c>a:
    for j in range(b,d+1):
      if i>a+1:
        X1[i][j-1]=((X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      else:
        X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      if j>=2:
        X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
  if d>b:
    X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
    X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
    X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
  if c>a:
    for j in range(b,d+1):
      X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
      if j>=2:
        X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
 X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
 X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
  if j>=2:
   X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
  else:
    X2[i][j-1]=0
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Time Limit Exceeded

Solution code:
Q = 998244353
#import sys
#input = sys.stdin.readline
def main():
    A, B, C, D = map( int, input().split())
    dp = [[0]*3002 for _ in range(3001)]
    dp[C][D] = 1
    for a in range(C-1,A-1,-1):
        dp[a][D] = dp[a+1][D]*D%Q
    for b in range(D-1,B-1,-1):
        dp[C][b] = dp[C][b+1]*C%Q
    for a in range(C-1,A-1,-1):
        z = dp[a+1][D]*a%Q
        for b in range(D-1,B-1,-1):
            dp[a][b] = (b*dp[a+1][b] + z)%Q
            z = (z + dp[a+1][b])*a%Q
    # for i in range(C+1):
    #     print(dp[i][:D+1])
    print(dp[A][B])
if __name__ == '__main__':
    main()