Problem: 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.

Examples

Input

1 1 2 2


Output

3


Input

2 1 3 4


Output

65


Input

31 41 59 265


Output

387222020

Solution (in PYTHON3):

Solution:
# https://atcoder.jp/contests/agc046/tasks/agc046_b
#
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def combination_mod(n, r, mod=998244353):
    # mod取りながらcombination
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


MOD = 998244353
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

A, B, C, D = read_ints()
i_max = C - A
j_max = D - B

'''
A+i,B+jまで広げたときを考える
このときの通りの総数は

更新則



これちがう↓
(1+(A+i-1,B+j)まで広げたの通りの総数)*(1+(A+i,B+j-1)の通りの総数)-1 となる
'''


dp = [[0] * (j_max + 1) for _ in ra(i_max + 1)]
# 初期値代入
for i in ra(i_max + 1):
    dp[i][0] = pow(B, i, MOD)

for j in ra(j_max + 1):
    dp[0][j] = pow(A, j, MOD)

# ループ
for i, j in product(range(1, i_max + 1), range(1, j_max + 1)):

    dp[i][j] = dp[i][j - 1] * (A + i) + dp[i - 1][j] * \
        (B + j) - (A + i - 1) * (B + j - 1)  # WA
    dp[i][j] = dp[i][j - 1] * (A + i) + dp[i - 1][j] * \
        (B + j) - (A + i - 1) * (B + j - 1) * dp[i - 1][j - 1]  # AC
    dp[i][j] %= MOD

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