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;

typedef long long ll;
#define int ll
typedef long double ld;

typedef pair<int,int> pii;
#define x first
#define y second

const int N=2e6+100,MOD=1e9+7;

int f[N],r[N];

int ppow(int x,int y=MOD-2)
{
    int ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%MOD;
        y>>=1;
        x=x*x%MOD;
    }
    return ans;
}

int solve(int x,int y)
{
//    cout<<x<<" "<<y<<" -> "<<flush;
    int ans=f[x+y+2]*r[x+1]%MOD*r[y+1]%MOD;
//    cout<<ans<<endl;
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    f[0]=1;
    r[0]=1;
    for(int i=1;i<N;i++)
        f[i]=f[i-1]*i%MOD,
        r[i]=ppow(f[i]);

    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    cout<<((solve(r2,c2)-solve(r2,c1-1)-solve(r1-1,c2)+solve(r1-1,c1-1))%MOD+MOD)%MOD;
}
