Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

R, C, K = map(int, input().split())

Items = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    Items[r][c] = v


DP = [[[-float('inf')] * 4 for _ in range(C + 1)] for __ in range(R + 1)]

for y in range(R+1):
    for x in range(C+1):
        if y == 0:
            DP[y][x][0] = 0
            continue
        if x == 0:
            DP[y][x][0] = 0
            continue
        if Items[y][x] == 0:
            for k in range(4):
                DP[y][x][0] = max(DP[y][x][0], DP[y - 1][x][k])
                if k != 0:
                    DP[y][x][k] = DP[y][x-1][k]
            DP[y][x][0] = max(DP[y][x][0], DP[y][x-1][0])
        else:
            for k in range(4):
                DP[y][x][0] = max(DP[y][x][0], DP[y - 1][x][k])
            DP[y][x][0] = max(DP[y][x][0], DP[y][x - 1][0])
            for k in range(1, 4):
                DP[y][x][k] = max(DP[y][x-1][k-1] + Items[y][x], DP[y][x-1][k])
                if k == 1:
                    DP[y][x][k] = max(DP[y][x][k], max(DP[y-1][x]) + Items[y][x])

print(max(DP[R][C]))

### FIXED CODE ###

R, C, K = map(int, input().split())

Items = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    Items[r][c] = v


DP = [[0] * 4 for _ in range(R + 1)]

for x in range(1, C+1):
    for y in range(1, R+1):
        v = Items[y][x]
        if v:
            DP[y][3] = max(DP[y][3], DP[y][2] + v)
            DP[y][2] = max(DP[y][2], DP[y][1] + v)
            DP[y][1] = max(max(DP[y][1], DP[y][0] + v), max(DP[y-1]) + v)
            DP[y][0] = max(DP[y][0], max(DP[y-1]))
        else:
            DP[y][0] = max(DP[y][0], max(DP[y-1]))

print(max(DP[R]))
### BUGGY CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    move = 2 * 10 ** 6
    for i in range(n):
        position = i
        for j in range(move):
            if s[position] == "R":
                position += 1
            else:
                position -= 1
        ans[position] += 1
    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    for i in range(n):
        if s[i] == "R":
            if i != (n - 1) and s[i + 1] == "L":
                ans[i] += 1
                for j in range(i - 2, -1, -2):
                    if s[j] == "R" and s[j + 1] == "R":
                        ans[i] += 1
                    else:
                        break
            for j in range(i + 2, n, 2):
                if s[j - 1] == "L" and s[j] == "L":
                    ans[i] += 1
                else:
                    break
        else:  # s[i] == "L"
            if i != 0 and s[i - 1] == "R":
                ans[i] += 1
                for j in range(i + 2, n, 2):
                    if s[j - 1] == "L" and s[j] == "L":
                        ans[i] += 1
                    else:
                        break
            for j in range(i - 2, -1, -2):
                if s[j] == "R" and s[j + 1] == "R":
                    ans[i] += 1
                else:
                    break
    print(*ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = 10 ** 9 + 7
N = int(input())
a = list(map(int, input().split()))
cnt = [0] * 60
for i in a:
    for j in range(60):
        cnt[j] += (i >> j) % 2
ans = 0
for b in range(60):
    ans += cnt[b] * (N - cnt[b]) << b
    ans %= INF
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10 ** 9 + 7
N = int(input())
a = list(map(int, input().split()))
cnt = [0] * 60
for i in a:
    for j in range(60):
        cnt[j] += (i >> j) % 2
ans = 0
for b in range(60):
    ans += cnt[b] * (N - cnt[b]) << b
    ans %= INF
print(ans)
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
a_val = collections.Counter(a)
count = 0

if len(a_val) > k:
    for i in range(len(a_val) - k):
        count += a_val.most_common()[-1-i][1]

print(count)

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(Counter(a).values(), reverse=True)

print(sum(a[k:]))
### BUGGY CODE ###

from math import gcd
from functools import reduce
from collections import defaultdict


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    for x in range(3, n, 2):
        yield x


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = defaultdict(int)
    for x in array:
        histogram[x] += 1

    for potential_prime in facs(MAX_A):
        count = sum(
            histogram[divider]
            for divider in range(potential_prime, MAX_A, potential_prime))
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

from math import gcd


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 2
    histgram = [0] * MAX_A
    for x in array:
        histgram[int(x)] += 1
    pairwise = True
    for divider in range(2, MAX_A):
        count = 0
        for counted in histgram[divider::divider]:
            count += counted
        if count > 1:
            pairwise = False
    if pairwise:
        return 'pairwise coprime'
    gcd_now = 0
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

n = int(input())
s = input()
passwords = []

firsts = []
firsts_seconds = []

for i in range(n-2):
    if len(firsts) == 10:
        break
    first =  s[i]
    if first in firsts:
        continue
    firsts.append(first)
    for j in range(i+1,n-1):
        second = s[j]
        first_second = first + second
        if first_second in firsts_seconds:
            continue

        firsts_seconds.append(first_second)
        for k in range(j+1, n):
            password = first_second + s[k]
            if password not in passwords:
                passwords.append(password)

print(len(passwords))

### FIXED CODE ###

n = int(input())
s = input()
passwords = []

firsts = []
firsts_seconds = [[]*10 for _ in range(10)]
firsts_seconds_thirds = [[]*10 for _ in range(100)]

for i in range(n-2):
    if len(firsts) == 10:
        break
    first =  s[i]
    if first in firsts:
        continue
    firsts.append(first)
    for j in range(i+1,n-1):
        if len(firsts_seconds[int(first)]) == 10:
            break
        second = s[j]
        first_second = first + second
        if first_second in firsts_seconds[int(first)]:
            continue
        firsts_seconds[int(first)].append(first_second)
        for k in range(j+1, n):
            password = first_second + s[k]
            if password not in firsts_seconds_thirds[int(first_second)]:
                firsts_seconds_thirds[int(first_second)].append(password)
                passwords.append(password)

print(len(passwords))
### BUGGY CODE ###

from collections import deque
#import time
#from sys import stdin

#start = time.time()#計測始
def main():
  s = str(input())
  ss = reversed(s)
  n=len(s)
  mlist=deque([0])
  slist=""
  for sss in ss:
    slist = sss + slist
    m = int(slist)%2019
    mlist.append(m)

  ll=len(mlist)
  l=len(set(mlist))

  print(ll-l)
  
main()

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
                ans %= mod
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break


### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))

k = []

for i in range(N):
    k.append(a[i])
    k.append(a[i]-1)
    k.append(a[i] + 1)

max = 0
for i in range(N):
    cnt = k.count(a[i])
    if cnt > max:
        max = cnt
    
    cnt = k.count(a[i]-1)
    if cnt > max:
        max = cnt

    cnt = k.count(a[i]+1)
    if cnt > max:
        max = cnt

print(max)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ary = [0 for _ in range(10**5)]

for i in range(n):
    if a[i] > 1:
        ary[a[i]-2] += 1
        ary[a[i]-1] += 1
    ary[a[i]] += 1

print(max(ary))
### BUGGY CODE ###

import collections

N = int(input())
S = []
for i in range(N):
    S.append(input())

#print(N,S)
#print("------------")
c = collections.Counter(S)
#print(c.most_common())
max_count = c.most_common()[0][1]

T = []
for i in range(N):
    if len(c.most_common()) > 1:
        if c.most_common()[i][1] == max_count:
            T.append(c.most_common()[i][0])
        else:
            break
    else:
        T.append(c.most_common()[0][0])
        break

T.sort()
for i in range(len(T)):
    print(T[i])

### FIXED CODE ###

import collections

N = int(input())
S = []
for i in range(N):
    S.append(input())

#print(N,S)
#print("------------")
c = collections.Counter(S)
#print(c.most_common())
temp = c.most_common()
max_count = temp[0][1]

T = []
for i in range(N):
    if len(temp) > 1:
        if temp[i][1] == max_count:
            T.append(temp[i][0])
        else:
            break
    else:
        T.append(temp[0][0])
        break

T.sort()
for i in range(len(T)):
    print(T[i])
### BUGGY CODE ###

import copy
S = input()
s = len(S)
MOD = 10**9+7
D = [0]*13
S = S[::-1]
for i in range(s):
    if i==0:
        if S[i]=="?":
            for j in range(10):
                D[j]+=1
        else:
            D[int(S[i])]+=1
    else:
        P = copy.copy(D)
        if S[i]=="?":
            p = 10**i
            for j in range(1,10):
                R = P[13-(j*p)%13:]+P[:13-(j*p)%13]
                for k in range(13):
                    D[k]+=R[k]
            continue
        else:
            p = int(S[i])*(10**i)
            D = P[13-p%13:]+P[:13-p%13]
print(D[5]%MOD)

### FIXED CODE ###

MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

DP = [[0]*13 for i in range(N)]
K = 1
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            if i==0:
                DP[0][(j*K)%13] = 1
            else:
                for k in range(13):
                    DP[i][(j*K+k)%13] += DP[i-1][k]
    else:
        j = int(S[i])*K
        if i==0:
            DP[0][(j*K)%13] = 1
        else:
            for k in range(13):
                DP[i][(j+k)%13] += DP[i-1][k]
    K = (K*10)%13
    for j in range(13):
        DP[i][j] = DP[i][j]%MOD
print(DP[N-1][5]%MOD)
### BUGGY CODE ###

# PROBLEM D
Q = int(input())
for _ in range(Q):
    a, b = sorted([int(s) for s in input().split()])
    c = 1
    sol = 0
    while True:
        d = (a * b) // c
        while c * d >= a * b:
            d -= 1
        if c > d:
            break
        if c < d:
            sol_ = (c != a) + (d != b)
        else:
            sol_ = (c != a) and (c != b)
        #print('candidate', c, d, sol_)
        sol += sol_
        c += 1
    print(sol)

### FIXED CODE ###

# PROBLEM D
Q = int(input())
for _ in range(Q):
    a, b = sorted([int(s) for s in input().split()])
    c_max = int((a * b) ** 0.5)
    if c_max * c_max == a * b:
        c_max -= 1
    sol = 2 * c_max
    if a <= c_max:
        sol -= 1
    if (c_max * c_max < a * b) and (c_max * (c_max + 1) >= a * b):
        sol -= 1
    print(sol)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
s = [input() for i in range(n)]
tmp = [defaultdict(int) for i in range(n)]

for j in range(len(s)):
    for k in s[j]:
        tmp[j][k] += 1
        
ans = 0
for i in range(0,len(s)):
    for j in range(i+1,len(s)):
        if(tmp[i]==tmp[j]):
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
dic = defaultdict(int)

n = int(input())
s = [input() for i in range(n)]

ans = 0
for j in range(len(s)):
    mozi = sorted(s[j])
    mozi_s = "".join(mozi)
    ans += dic[mozi_s]
    dic[mozi_s] += 1
    
print(ans)
### BUGGY CODE ###

from itertools import permutations
from heapq import heappush


def solve(n, m, r):
    ans = []
    d = [[float("inf")]*n for _ in range(n)]
    rx = list(map(int, input().split()))
    rx = list(map(lambda x: x-1, rx))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        heappush(ans, from_p1_to_pr)

    return ans[0]


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))


### FIXED CODE ###

from itertools import permutations


def solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dt = d[i][k] + d[k][j]
                if dt < d[i][j]:
                    d[i][j] = dt

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

anss = [0 for _ in range(n-1)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    for k in range(1, n): 
        for i in range(n):
            if dist[i]-dist[start] == k:
                anss[k-1] += 1
    
for i in range(n):
    bfs(i)
for i in range(n-1):
    print(anss[i]//2)


### FIXED CODE ###

#!/usr/bin/env python3
# TLE解
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

ans = [0 for _ in range(n)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    # for k in range(1, n):
    #     for i in range(n):
    #         if dist[i]-dist[start] == k:
    #             ans[k-1] += 1

    for i in range(n):
        ans[dist[i]] += 1
    
for i in range(n):
    bfs(i)
for i in range(1, n): 
    print(ans[i]//2)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
for i in range(n):
    s *= a[i]
    
if s > 10**18:
    print(-1)
else:
    print(s)
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
f = 1
if 0 in a:
    print(0)
else:
    for i in a:
        s *= i
        if s > 10**18:
            print(-1)
            break
            
    if s <= 10**18:
        print(s)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
a.sort()

if n%2==1 and collections.Counter(a)[0]==1:
    for i in range(2,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
    else:
        print(2**(n//2)%(10**9+7))
elif n%2==0:
    for i in range(1,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
    else:
        print(2**(n//2)%(10**9+7))
else:
    print(0)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
if n%2==1:
    b=[i for i in range(2,n,2)]
    b=b*2
    b.sort()
    #print(a,b)
    b=[0]+b
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
elif n%2==0:
    b=[i for i in range(1,n,2)]
    b=b*2
    b.sort()
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
### BUGGY CODE ###

N,M = map(int,input().split())
job = {}
for i in range(N):
    A,B = map(int,input().split())
    job.setdefault(A,[]).append(B)
ans = 0
last = min(job.keys())
for i in range(last,M+1):
    if(job[i] != []):
        today = max(job[i])
        ans += today
        job[i].remove(today)
    job.setdefault(i+1,[]).extend(job[i])
print(ans)

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
AB = sorted([list(map(int,input().split())) for _ in range(N)])

option = []
ans = 0
j = 0
for i in range(1,M+1):
    while j != N and AB[j][0] <= i: 
        heapq.heappush(option,-AB[j][1])
        j += 1
    if len(option) != 0:
        ans -= heapq.heappop(option)
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
ch = [[0] * w for i in range(h)]
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == "#" and ch[sx][sy] == 0:
            cnt = 1
            nu = 0
            ch[sx][sy] = 1
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while len(now) != 0:
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            nu += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                            if lis[x-1][y] == "#" and ch[x-1][y] == 0:
                                cnt += 1
                                ch[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            nu += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                            if lis[x+1][y] == "#" and ch[x+1][y] == 0:
                                cnt += 1
                                ch[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            nu += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                            if lis[x][y-1] == "#" and ch[x][y-1] == 0:
                                cnt += 1
                                ch[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            nu += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                            if lis[x][y+1] == "#" and ch[x][y+1] == 0:
                                cnt += 1
                                ch[x][y+1] = 1
                now = tmp
            ans += nu * cnt
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

dxdy = {(-1, 0), (1, 0), (0, -1), (0, 1)}

h,w = map(int,input().split())
s = [str(input()) for i in range(h)]

ch = [[0] * w for i in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if ch[i][j] == 0:
            black,white = 0,0
            q = [(i,j)]
            while q:
                y,x = q.pop()
                if ch[y][x] == 0:
                    if s[y][x] == "#":black += 1
                    else:white += 1
                    ch[y][x] = 1
                    for dx,dy in dxdy:
                        if 0 <= x + dx < w and 0 <= y + dy < h and ch[y+dy][x+dx] == 0 and s[y+dy][x+dx] != s[y][x]:
                            q.append((y+dy,x+dx))
            ans += black * white

print(ans)
### BUGGY CODE ###

mod = 998244353
A, B, C, D = map(int,input().split())
dp = [[0 for i in range(D-B+1)] for j in range(C-A+1)]
dp[0][0] = 1

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

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

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

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

### FIXED CODE ###

mod = 998244353
A, B, C, D = map(int,input().split())
dp = [[0 for i in range(D-B+1)] for j in range(C-A+1)]
dp[0][0] = 1

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

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

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

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