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:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import copy
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    a, b, c, d = map(int, input().split())
    MAX = 998244353
    rowcol = [[0]*(d+1) for _ in range(c+1)]
    rowcol[a][b] = 1
    row2 = [[0]*(d+1) for _ in range(c+1)]
    col2 = [[0]*(d+1) for _ in range(c+1)]
    for i in range(b+1, d+1):
        rowcol[a][i] = (rowcol[a][i-1]*a)%MAX
    
    for j in range(a+1, c+1):
        for i in range(b, d+1):
            if i == b:
                rowcol[j][b] = (rowcol[j-1][b]*b)%MAX
            else:
                rowcol[j][i] = ((rowcol[j-1][i]+row2[j-1][i])*(i-1))%MAX
                row2[j][i] = (rowcol[j][i-1]+col2[j][i-1]+row2[j][i-1]*j)%MAX
                col2[j][i] = (rowcol[j-1][i]+col2[j-1][i]*i+row2[j-1][i])%MAX
    
    print((rowcol[c][d]+row2[c][d]+col2[c][d])%MAX)