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

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

dp = [[0] * (D+1) for j in range(C+1)]

dp[A][B] = 1

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

print(dp[C][D])

Solution (Python):
A,B,C,D = map(int, input().split())
MOD = 998244353
MAX_SIZE = 3010
dp = [[0] * MAX_SIZE for _ in range(MAX_SIZE)]

dp[A][B] = 1
for h in range(A, C+1):
    for w in range(B, D+1):
        if h == A and w == B: continue
        dp[h][w] = dp[h-1][w] * w + dp[h][w-1] * h - dp[h-1][w-1] * (h-1) * (w-1)
        dp[h][w] %= MOD

print(dp[C][D])

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

dp=[[1]*(d-b+1) for _ in range(c-a+1)]
mod=998244353 
for h in range(1,c-a+1):
    dp[h][0]=pow(b,h,mod)
for w in range(1,d-b+1):
    dp[0][w]=pow(a,w,mod)
for w in range(1,d-b+1):
    for h in range(1,c-a+1):
        
        dp[h][w]=dp[h][w-1]*(h+a)+dp[h-1][w]*(w+b)-dp[h-1][w-1]*(w+b-1)*(h+a-1)
        dp[h][w]%=mod

print(dp[c-a][d-b])

Solution (Python):


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 + 1):
  for j in range(b, d + 1):
    if i == a and j == b:
      continue
    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[-1][-1] % MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    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, c + 1):
        for j in range(b, d + 1):
            if i == a and j == b:
                continue
            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[-1][-1] % mod)


if __name__ == '__main__':
    resolve()

Solution (Python):
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])

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


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

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

    return(dp[c][d])


    return None

if __name__ == '__main__':
    a,b,c,d = map(int,ipt().split())
    print(main(a,b,c,d))

Solution (Python):
from sys import stdin


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()

Solution (Python):
a,b,c,d=map(int,input().split())
mod=998244353
dp=[[0]*(c+1) for i in range(d+1)]
dp[b][a]=1
for i in range(b,d+1):
  for j in range(a,c+1):
    if i==b and j==a:
      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[-1][-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    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, C + 1):
        for j in range(B, D + 1):
            if i == A and j == B:
                continue
            dp[i][j] = dp[i][j - 1] * i + dp[i - 1][j] * j - dp[i - 1][j - 1] * (i - 1) * (j - 1)
            dp[i][j] %= mod

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


if __name__ == '__main__':
    resolve()

Solution (Python):
a,b,c,d=map(int,input().split())
s=[[0]*3001for i in range(3001)]
s[a][b]=1
m=998244353
for i in range(3000):
    for j in range(3000):
        s[i+1][j+1]+=(s[i+1][j]*(i+1)+s[i][j+1]*(j+1)-s[i][j]*i*j)%m
print(s[c][d])

Solution (Python):

p = 998244353

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

print(dp[c][d])

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    MOD = 998244353
    a, b, c, d = map(int, readline().split())
    h, w = c - a, d - b

    dp = [[1] * (d + 1) for _ in range(c + 1)]

    for row in range(a + 1, c + 1):
        dp[row][b] = (dp[row - 1][b] * b) % MOD

    for col in range(b + 1, d + 1):
        dp[a][col] = (dp[a][col - 1] * a) % MOD

    for row in range(a + 1, c + 1):
        for col in range(b + 1, d + 1):
            x = dp[row - 1][col] * col + dp[row][col - 1] * row
            y = dp[row - 1][col - 1] * (row - 1) * (col - 1)
            dp[row][col] = (x - y) % MOD

    print(dp[c][d])


if __name__ == '__main__':
    main()

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

P=998244353

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

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

print(dp[C][D])

Solution (Python):
A, B, C, D = map(int,input().split())
P = 998244353

memo = [[0]*(D+1) for _ in range(C+1)]

memo[A][B] = 1

for i in range(A,C+1):
  for j in range(B,D+1):
    memo[i][j] += i*memo[i][j-1] + j*memo[i-1][j] - (i-1)*(j-1)*memo[i-1][j-1]
    memo[i][j] %= P
    
print(memo[C][D])

Solution (Python):
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])

Solution (Python):
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(1,c+1):
    for j in range(1,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[-1][-1])

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

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

Solution (Python):

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])

Solution (Python):
a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
X0=[[0]*d for i in range(c)]
X1=[[0]*d for i in range(c)]
X2=[[0]*d for i in range(c)]
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=amari(X0[a-1][j-1]*(a-1))
 X1[a-1][j]=amari(X0[a-1][j-1]+X1[a-1][j-1]*(a-1))
 X2[a-1][j]=amari(X1[a-1][j-1]+X2[a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=amari((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j)
  if j>=2:
   X2[i][j-1]=amari(X1[i][j-2]+X2[i][j-2] *(i+1))
print(amari(X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1]))

Solution (Python):
Q = 998244353


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
    
    
    print(dp[A][B])
if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b,c,d = LI()

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

    for i in range(a,c+1):
        for j in range(b,d+1):
            if a < i:
                dp[i][j] += dp[i-1][j] * j % mod2
            if b < j:
                dp[i][j] += dp[i][j-1] * i % mod2
            if a < i and b < j:
                dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1) % mod2

    return dp[c][d] % mod2


print(main())

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

A, B, C, D = mapint()
mod = 998244353

dp = [[0]*D for _ in range(C)]
dp[A-1][B-1] = 1

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

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

Solution (Python):
def main():
    A, B, C, D = map(int, input().split())
    mod = 998244353

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

    print(dp[-2][-2])


main()

Solution (Python):
A,B,C,D = map(int,input().split())
MOD = 998244353

dp = [[0 for _ in range(D+1)] for _ in range(C+1)]
dp[A][B] = 1
for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A or j > B:
      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

ans = dp[C][D]
print(ans)

Solution (Python):
A,B,C,D = map(int,input().split())
MOD = 998244353

dp = [[0 for _ in range(D+1)] for _ in range(C+1)]
dp[A][B] = 1


for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A:
      dp[i][j] += dp[i-1][j]*j
    if j > B:
      dp[i][j] += dp[i][j-1]*i
    if i > A and j > B:
      dp[i][j] -= dp[i-1][j-1]*(i-1)*(j-1)
    dp[i][j] %= MOD

ans = dp[C][D]
print(ans)

Solution (Python):
A, B, C, D = (int(x) for x in input().split())
MOD = 998244353
dp = [[0] * (D + 1) for _ in range(C + 1)]
dp[A][B] = 1
for i in range(A, C + 1):
    for j in range(B, D + 1):
        if i == A and j == B:
            continue
        if i > A:
            dp[i][j] += dp[i - 1][j] * j
        if j > B:
            dp[i][j] += dp[i][j - 1] * i
        if i > A and j > B:
            dp[i][j] -= dp[i - 1][j - 1] * (i - 1) * (j - 1)
        dp[i][j] %= MOD

print(dp[C][D])

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

dp1=[[0]*(d+1) for _ in range(c+1)]
dp2=[[0]*(d+1) for _ in range(c+1)]

for i in range(b+1,d+1):
  if a==1:
    dp1[a][i]=1 if i==b+1 else 0
    dp2[a][i]=0 if i==b+1 else 1
  else:
    dp1[a][i]=(pow(a-1,i-b-1,mod)*(i-b))%mod
    dp2[a][i]=(pow(a,i-b,mod)-dp1[a][i])%mod
for i in range(a+1,c+1):
  dp1[i][b]=pow(b,i-a,mod)
  dp2[i][b]=0
dp2[a][b]=1
for i in range(a+1,c+1):
  for j in range(b+1,d+1):
    dp1[i][j]=(j*(dp1[i-1][j]+dp2[i-1][j]))%mod
    dp2[i][j]=(dp1[i][j-1]+dp2[i][j-1]*i)%mod
print((dp1[c][d]+dp2[c][d])%mod)

"""
print('dp1')
for x in dp1:
  print(x)
print('dp2')
for x in dp2:
  print(x)
"""

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

MOD = 998244353

dp = [[0]*3005 for i in range(3005)]
dp[c][d] = 1
for i in range(d,0,-1):
    dp[c][i-1] = dp[c][i]*c%MOD
for i in range(c-1,-1,-1):
    x = 0
    for j in range(d,-1,-1):
        dp[i][j] = (j*dp[i+1][j]+x) % MOD
        x += dp[i+1][j]
        x *= i
        x %= MOD


print(dp[a][b])

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

dp1 = [[0 for j in range(d)] for i in range(c)] 
dp2 = [[0 for j in range(d)] for i in range(c)] 
dp2[a-1][b-1] = 1

for i in range(a-1, c):
    for j in range(b-1, d):
        if i==a-1 and j==b-1: continue
        if i-1 >= 0:
            dp1[i][j] = (j+1)*(dp1[i-1][j]+dp2[i-1][j])
            dp1[i][j] %= mod
        if j-1 >= 0:
            dp2[i][j] = dp1[i][j-1] + (i+1)*dp2[i][j-1]
            dp2[i][j] %= mod

ans = (dp1[c-1][d-1] + dp2[c-1][d-1]) % mod
print(ans)

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



p=998244353
dp=[[0]*(D+1) for _ in range(C+1)]



for h in range(A,C+1):
    for w in range(B,D+1):
        if h==A and w==B:
            dp[A][B]=1
            continue

        if h>A and w>B:
            x=dp[h][w-1]*h
            y=dp[h-1][w]*w
            z=dp[h-1][w-1]*(h-1)*(w-1)
            sub=x+y-z
            dp[h][w]=(sub)%p
        elif h==A:
            dp[h][w]=(dp[h][w-1]*h)%p
        else:
            dp[h][w]=(dp[h-1][w]*w)%p


print(dp[C][D])

Solution (Python):

import sys
MOD = 998244353
def main(A, B, C, D):
    I, J = C - A, D - B
    dp = [[0] * (I + 1) for _ in range(I + J + 1)]
    dp[0][0] = 1
    for k in range(1, I + J + 1):
        for i in range(min(I, k) + 1):
            j = k - i
            v = dp[k - 1][i - 1] * (j + B) % MOD if i >= 1 else 0
            h = dp[k - 1][i] * (i + A) % MOD
            d = dp[k - 2][i - 1] * (i + A - 1) * (j + B - 1) if k >= 2 and i >= 1 else 0
            dp[k][i] = (v + h - d) % MOD
    print(dp[I + J][I])

if __name__ == '__main__':
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    main(A, B, C, D)

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

MOD = 998244353





dp = [[0 for _ in range(D + 1)] for _ in range(C + 1)]  




dp[A][B] = 1




for i in range(A + 1, C + 1):
    dp[i][B] = (B * dp[i - 1][B]) % MOD




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




for i in range(A + 1, C + 1):
    for j in range(B + 1, D + 1):
        dp[i][j] = (i * dp[i][j - 1]) % MOD
        dp[i][j] = (dp[i][j] + (j * dp[i - 1][j]) % MOD) % MOD
        dp[i][j] = (dp[i][j] - ((i - 1) * (j - 1) * dp[i - 1][j - 1]) % MOD) % MOD

print(dp[C][D])

Solution (Python):

"""
https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-20agc046
「操作列の結果、完成図としてありうるものを数えよ」
という問題は、複数の操作後の完成図が同じ結果を取りうることを考慮し、
・完成図としてあり得るパターンの同値な言い換えを探す
・操作に制約を加えても同じ完成図を作成できることが一意になる
のどちらかを目指して、考察していく。

以下、問題の「縦を選んだ場合のマスの変化」は上ではなく下として考える。

ケース2の
2 1 3 4
について考える。
これは縦に1回と横に3回の追加を行うが、
実は縦の制御について、最も左端に存在する黒タイルについて場合分けをして良い。
w???
w???
b???
の盤面について考えた時、これは初手に縦の操作を選ぶことで達成できるが、
そうでないような操作で上図と同じような盤面になったとして、実は左下の位置が
黒になるような場合、？の位置もまた同じように決定されるので、そのような
操作は考慮しなくて良いことが分かる。

そのような操作とは、つまり、"縦方向の拡張を最速で行わなかった"ような操作である。
考察すべき2つめの条件、操作に制約を加えても同じ完成図を作成できることが一意になる
を達成することができた。

この時の?の組み合わせは、横拡張3回のうち、すべての拡張で3つを選べるので、
3*3通り
である。
次は、一番下の行で、初めて黒が出る位置を1つずつずらして考えていく。
w???
w???
wb??

この場合、右に1回横拡張を挟んで、すぐさま縦拡張,そのあと横拡張を2回行うので、
2*3*3

w???
w???
wwb?

2*2*3

w???
w???
wwwb

2*2*2

よって合計65通りとなる。

この操作をdpによって拡張する。
具体的には、
dp[i][j]:横幅iの時点で残りの縦幅がjの時、縦幅を利用する際の通し数
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
A,B,C,D = map(int,readline().split())
mod = 998244353
dp0 = [[0] * (D + 1) for _ in range(C + 1)]
dp1 = [[0] * (D + 1) for _ in range(C + 1)]
 
 
dp0[A][B] = 1
 
for x in range(A, C + 1):
    for y in range(B, D + 1):
        if x == A and y == B:
            continue
        dp0[x][y] = (dp0[x][y - 1] * x + dp1[x][y - 1] * 1) % mod
        dp1[x][y] = (dp0[x - 1][y] * y + dp1[x - 1][y] * y) % mod

ans = (dp0[C][D] + dp1[C][D]) % mod
print (ans)

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

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

MOD = 998244353

dp0 = [[0] * (D + 1) for _ in range(C + 1)]
dp1 = [[0] * (D + 1) for _ in range(C + 1)]


dp0[A][B] = 1

for x in range(A, C + 1):
    for y in range(B, D + 1):
        if x == A and y == B:
            continue
        dp0[x][y] = (dp0[x][y - 1] * x + dp1[x][y - 1] * 1) % MOD
        dp1[x][y] = (dp0[x - 1][y] * y + dp1[x - 1][y] * y) % MOD




ans = (dp0[C][D] + dp1[C][D]) % MOD
print (ans)

Solution (Python):
from itertools import*;a,b,c,d=map(int,input().split());D=[[0]*6011for _ in[0]*6011];D[a][b]=1
for i,j in product(range(c+d),repeat=2):
 D[i+1][j+1]+=(D[i+1][j]*(i+1)+D[i][j+1]*(j+1)-D[i][j]*i*j)%998244353
print(D[c][d])

Solution (Python):
a,b,c,d=map(int,input().split());x=range(c+d);D=[[0]*6011for _ in[0]*6011];D[a][b]=1
for i in x:
 for j in x:D[i+1][j+1]+=(D[i+1][j]*(i+1)+D[i][j+1]*(j+1)-D[i][j]*i*j)%998244353
print(D[c][d])

Solution (Python):
a,b,c,d=map(int, input().split())
mod=998244353
if a==c and b==d:
  print(1)
  exit()
else:
  dp=[[0]*(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
      else:
        dp[i][j]=dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j]%=mod
print(dp[c][d])

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

Solution (Python):
mod = 998244353

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

dp = [0] * B + [pow(A, i, mod) for i in range(D + 1 - B)]
for a in range(A + 1, C + 1):
    T = [0] * (D + 1)
    for b in range(B, D + 1):
        T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
    dp = T

print(dp[D])

Solution (Python):
mod = 998244353

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

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

for a in range(A + 1, C + 1):
    T = [0] * (D + 1)
    for b in range(B, D + 1):
        T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
    dp = T

print(dp[D])

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

MOD=998244353


DP=[[0]*(D-B+1) for _ in range(C-A+1)]
DP[0][0]=1

for i in range(1,C-A+1):
    DP[i][0]=DP[i-1][0]*B
    DP[i][0]%=MOD
for i in range(1,D-B+1):
    DP[0][i]=DP[0][i-1]*A
    DP[0][i]%=MOD

for i in range(1,min(C-A,D-B)+1):
    for j in range(i,C-A+1):
        DP[j][i] = DP[j-1][i]*(B+i) + DP[j][i-1]*(A+j)-DP[j-1][i-1]*(B+i-1)*(A+j-1)
        DP[j][i]%=MOD
    for j in range(i+1,D-B+1):
        DP[i][j] = DP[i-1][j]*(B+j) + DP[i][j-1]*(A+i)-DP[i-1][j-1]*(B+j-1)*(A+i-1)
        DP[i][j]%=MOD


print(DP[-1][-1])

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

a, b, c, d = MAP()
dp0 = list2d(c+1, d+1, 0)
dp1 = list2d(c+1, d+1, 0)

dp1[a][b] = 1
for i in range(a, c+1):
    for j in range(b, d+1):
        dp0[i][j] += dp0[i-1][j] * j
        dp0[i][j] += dp1[i-1][j] * j
        dp1[i][j] += dp1[i][j-1] * i
        dp1[i][j] += dp0[i][j-1]
        dp0[i][j] %= MOD
        dp1[i][j] %= MOD
ans = (dp0[c][d] + dp1[c][d]) % MOD
print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

a, b, c, d = MAP()
dp = list2d(c+1, d+1, 0)

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] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= MOD
ans = dp[c][d]
print(ans)

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

dp = [[0] * (D + 1) for _ in range(C + 1)]

for i in range(A, C + 1):
    for j in range(B, D + 1):
        if (i, j) == (A, B):
            dp[i][j] = 1
        else:
            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])

Solution (Python):
def main():
    MOD = 998244353

    A, B, H, W = map(int, input().split())

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[A][B] = 1

    for h in range(A, H + 1):
        for w in range(B, W + 1):
            if h == A and w == B: continue
            t = 0
            if h > A:
                t += dp[h - 1][w] * w
            if w > B:
                t += dp[h][w - 1] * h
            if h > A and w > B:
                t -= dp[h - 1][w - 1] * (h - 1) * (w - 1)
            dp[h][w] = t % MOD

    print(dp[H][W])


if __name__ == '__main__':
    main()

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

mod = 998244353

dp = [[-1 for i in range(d+1)] for j in range(c+1)]
for i in range(a+1):
    for j in range(b+1):
        dp[i][j] = 1
def doubling(n, m, modulo=0):
    y = 1
    base = n
    tmp = m
    while tmp:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y
for i in range(b, d):
    dp[a][i+1] = dp[a][i] * a
    dp[a][i+1] %= mod
for i in range(a, c):
    dp[i+1][b] = dp[i][b] * b
    dp[i+1][b] %= mod
for i in range(a+1, c+1):
    for j in range(b+1, d+1):
        dp[i][j] = j*dp[i-1][j] + i*dp[i][j-1] - (i-1)*(j-1)*dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[c][d])

Solution (Python):

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

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

dp0 = [0] * (c-a+1)
dp1 = [1]
for i in range(c-a):
    dp1.append(dp1[-1] * b % mod)

for j in range(1, d-b+1):
    new_dp0 = [(dp0[0] * a + dp1[0]) % mod]
    new_dp1 = [dp1[0] * (a-1) % mod]
    for i in range(1, c-a+1):
        new_dp0.append((dp0[i] * (a+i) + dp1[i]) % mod)
        new_dp1.append((new_dp0[-2] + new_dp1[-1]) * (b+j) % mod)

    dp0 = new_dp0
    dp1 = new_dp1

print((dp0[-1] + dp1[-1]) % mod)

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    A, B, C, D = read_values()

    dp = [[0 for _ in range(D - B + 1)] for _ in range(C - A + 1)]
    dp[0][0] = 1

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

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

    print(dp[C - A][D - B] % mod)


if __name__ == "__main__":
    main()

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

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] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])

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


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]+=dp[i][j-1]*i
        dp[i][j]-=dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j]%=mod


print(dp[c][d])

Solution (Python):
A, B, C, D = map(int, input().split())
MOD = 998244353

dp = [[0] * (D + 2) for _ in range(C + 2)]
dp[A][B] = 1

for h in range(A, C + 1):
    for w in range(B, D + 1):
        d = dp[h][w] % MOD
        dp[h + 1][w] += d * w
        dp[h][w + 1] += d * h
        dp[h + 1][w + 1] -= d * w * h % MOD
print(dp[C][D] % MOD)

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

if __name__ == '__main__':
	main()

Solution (Python):
A, B, C, D = map(int, input().split())
MOD = 998244353

dp = [[0] * (D + 2) for _ in range(C + 2)]
dp[A][B] = 1

for h in range(A, C + 1):
    for w in range(B, D + 1):
        d = dp[h][w] % MOD
        dp[h + 1][w] += d * w
        dp[h][w + 1] += d * h
        dp[h + 1][w + 1] -= d * w * h % MOD
print(dp[C][D] % MOD)

Solution (Python):
mod = 998244353

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

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


for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        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])

Solution (Python):
a,b,c,d = map(int,input().split())
ans = 0
dp = [[0]*(d+1) for i in range(c+1)]
mod = 998244353
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b] * b % mod
for i in range(b+1,d+1):
    dp[a][i] = dp[a][i-1] * a % mod
for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        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])