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;
const int M=1e6+10;
typedef long long ll;
const ll MOD=1e9+7;
ll fact[M*2];

ll quick_mod(ll a,ll b,ll mod){
	ll ans=1;
	a%=mod;
	while(b){
		if(b&1)ans=(ans%mod * a%mod)%mod;
		a=(a%mod * a%mod)%mod;
		b>>=1;
	}
	return ans%mod;
}
ll get_inv(ll x){
	return quick_mod(x,MOD-2,MOD);
}

ll C_mod(ll n,ll k){
	return (fact[n] * get_inv(fact[k])%MOD * get_inv(fact[n-k])%MOD)%MOD;
}

int main(int argc, char const *argv[])
{
	ll c1,r1,c2,r2;
	cin>>r1>>c1>>r2>>c2;
	fact[0]=1;
	for(int i=1;i<=r2+c2+2;i++)fact[i]=(ll)fact[i-1]*i%MOD;//阶乘
	ll ans=(C_mod(r1+c1,c1)+C_mod(r2+c2+2,c2+1)-C_mod(c1+r2+1,c1)-C_mod(r1+c2+1,c2+1)+MOD)%MOD;
	printf("%lld\n",ans%MOD);
	return 0;
}