Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.

Let us define a function f(r, c) as follows:

* f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)



Given are integers r_1, r_2, c_1, and c_2. Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Constraints

* 1 ≤ r_1 ≤ r_2 ≤ 10^6
* 1 ≤ c_1 ≤ c_2 ≤ 10^6
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


r_1 c_1 r_2 c_2


Output

Print the sum of f(i, j) modulo (10^9+7).

Examples

Input

1 1 2 2


Output

14


Input

314 159 2653 589


Output

602215194
r1, c1, r2, c2 = map(int, input().split())

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p

g = [0]*M
p = 0
for i in range(1, M):
  g[i] = p = ((p+1)*2-1)%mod

def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = g[R+C+1] % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = g[C-c]
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = g[R-r]
        ret = (ret-x1*x2) % mod

    return ret

ans = count(r2, c2) + count(r1-1, c1-1) - count(r2, c1-1) - count(r1-1, c2)
ans %= mod
print(ans)