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
#include <bits/stdc++.h>

using namespace std;

typedef long long lli;

const int N = 2000000 + 10;
const int MOD = 1000000007;

int f[N], fr[N], p[N];

int exp(int x, int n)
{
	int tmp;
	if (n == 0) return 1;
	tmp = exp(x, n / 2);
	tmp = 1LL * tmp * tmp % MOD;
	if (n % 2) tmp = 1LL * tmp * x % MOD;
	return tmp;
}

int calc(int n, int m)
{
	return 1LL * f[n] * fr[m] % MOD * fr[n-m] % MOD;
}

int main()
{
	int res, r1, c1, r2, c2, n, m, a, b, i, j;
	cin>>r1>>c1>>r2>>c2;
	n = r2 + c2 + 2;
	f[0] = fr[0] = p[0] = 1;
	for (i=1; i<=n; i++) 
	{
		f[i] = 1LL * f[i-1] * i % MOD;
		fr[i] = exp(f[i], MOD - 2);
		p[i] = p[i-1] * 2LL % MOD;
	}
	a = (calc(r2 + c2 + 2, r2 + 1) + calc(r1 + c1, r1)) % MOD;
	b = (calc(r1 + c2 + 1, r1) + calc(r2 + c1 + 1, c1)) % MOD;
	res = ((a - b) % MOD + MOD) % MOD;
	cout<<res<<endl;
	return 0;
}