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;
#define LL long long
#define fs first
#define sc second
#define P pair<int, int>
#define mk_p make_pair
const int mod = 1e9 + 7;
const int N = 2e6 + 11;
int fac[N], inv[N];
int r1, c1, r2, c2;
int M(int x, int y){
	return 1LL * x * y % mod;
}
int A(LL x, LL y){
	return (x + y) % mod;
}
LL C(int n, int m){
	if(n < m)return 0;
	return M(fac[n], M(inv[m], inv[n-m]));
}
int main(){
	cin>>r1>>c1>>r2>>c2;
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for(int i = 2;i <= 2e6 + 1; i++){
		fac[i] = M(fac[i-1], i);
		inv[i] = (mod - 1LL * mod / i * inv[mod%i] % mod) % mod;
	}
	for(int i = 2;i <= 2e6 + 1; i++){
		inv[i] = M(inv[i], inv[i-1]);
	}
	LL ans = 0;
	for(int i = r1;i <= r2; i++){
		ans = A(ans, C(i + c2 + 1, c2) - C(i + c1, c1 - 1) + mod);
//		printf("i=%d ans=%d\n", i, ans);
	}
	cout<<ans<<endl;
	return 0;
}