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>
#define fastio() ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef long double ld;

const ll mod = 1e9+7;


ll fpow(ll a, ll b, ll p){
	ll res = 1; a%=p;
	while(b>0){
		if (b&1) res = res*a%p;
		a = a*a%p;
		b>>=1;
	}
	return res;
}

const int maxn = 2e6+5;
ll f[maxn], rcnt[maxn], ccnt[maxn];
ll r1, r2, c1, c2;

ll inv(ll n) { return fpow(n, mod-2, mod); } 
ll ncr(ll n, ll k, ll p) { 
    if (k == 0 or n == k) return 1;
    ll ans = f[n]*inv(f[k])%p * inv(f[n-k])%p;
    return ans%p;
} 


int main(){
	f[0] = f[1] = 1;
	for(ll i = 2; i<maxn; i++) f[i] = (f[i-1]*i)%mod;
	cin >> r1 >> c1 >> r2 >> c2;
	ll ans = 0;
	for(ll row = r1+1; row<=r2+1; row++){
		ans += ncr(row+c2, c2, mod);
		ans -= ncr(row+c1-1, c1-1, mod);
		ans = ((ans%mod)+mod)%mod;
	}
	ans = ((ans%mod)+mod)%mod;
	cout << ans << endl;
	return 0;
}
