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 <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

constexpr ll mod = 1e9 + 7;
ll fact[2000010], facti[2000010];
ll pow(ll n, ll e) {
	ll v = 1;
	while (e) {
		if (e & 1)
			v = (v * n) % mod;
		n = (n * n) % mod;
		e /= 2;
	}
	return v;
}
ll comb(ll n, ll r) {
	return (fact[n] * facti[n - r] % mod) * facti[r] % mod;
}
ll f(ll r, ll c) {
	ll s = 0;
	for (int i = 0; i <= r; i++)
		s += comb(i + c, c);
	for (int i = 0; i <= c; i++)
		s += comb(i + r, r);
	return (s - 1 + mod) % mod;
}

int c1, c2, r1, r2;
int main() {
	scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
	fact[0] = 1;
	for (int i = 1; i <= 2000000; i++)
		fact[i] = fact[i - 1] * i % mod;
	facti[2000000] = pow(fact[2000000], mod - 2);
	for (int i = 2000000; 1 <= i; i--)
		facti[i - 1] = facti[i] * i % mod;
	printf("%lld\n", ((f(r2,c2) - f(r2,c1-1) - f(r1-1, c2) + f(r1-1, c1-1)) % mod + mod) % mod);
}