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 ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll fc[2002002]={1ll},nv[2002002]={1ll};

ll rwpw(ll a, ll p = MOD-2){
	ll ret = 1ll;
	while(p){
		if(p&1){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

int main(void){
	int r[2],c[2],i;
	ll x,y,ans=0ll;
	for(i=1; i<=2000020; ++i){
		fc[i] = fc[i-1]*i%MOD;
		nv[i] = rwpw(fc[i]);
	}
	for(i=0; i<2; ++i){
		cin >> r[i] >> c[i];
	}
	for(i=r[0]; i<=r[1]; ++i){
		x = fc[c[0]+i]*nv[c[0]]%MOD;
		y = fc[c[1]+i]*nv[c[1]]%MOD;
		mul_mod(x,c[0]);
		mul_mod(y,c[1]+i+1);
		add_mod(y,MOD-x);
		mul_mod(y,nv[i+1]);
		add_mod(ans,y);
	}
	cout << ans << endl;
	return 0;
}
