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<iostream>
using namespace std;

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 1000000007
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const int maxn=2e6+10;

int x1,y1,x2,y2;
ll tmp[maxn];

ll inv(ll x,int p) {
	if (p==0) return 1;
	if (p%2==1) return x*inv(x*x%mod,p/2)%mod;
	else return inv(x*x%mod,p/2); 
}

ll f(int x,int y) {
	return tmp[x+y]*inv(tmp[x],mod-2)%mod*inv(tmp[y],mod-2)%mod;
}

ll solve(int x,int y) {
	ll res=0;
	for (int i=1;i<=x+1;i++) (res+=f(i,y))%=mod;
	return res;
}

int main(){    
	tmp[0]=1;
	for (int i=1;i<maxn;i++) tmp[i]=(tmp[i-1]*(ll)i)%mod;
	cin>>x1>>y1>>x2>>y2;
	ll ans=solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1);
	ans%=mod;
	if (ans<0) ans+=mod;
	cout<<ans;
	return 0;
}
