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<cstdio>
const int Mod=1e9+7;
inline int MyPow(int a,int b){
    int ss=1;
    for(;b;b>>=1){
        if(b&1) ss=1ll*ss*a%Mod;
        a=1ll*a*a%Mod;
    }
    return ss;
}
inline int C(const int n,int m){
    if(n<m) return 0;
    if(n==m) return 1;
    if(m>n-m) m=n-m;
    int sn=1,sm=1;
    for(register int i=0;i<m;i++){
        sn=1ll*(n-i)%Mod*sn%Mod;
        sm=1ll*(m-i)%Mod*sm%Mod;
    }
    return 1ll*sn*MyPow(sm,Mod-2)%Mod;
}
inline int Lucas(const int n,const int m){
    if(!m) return 1;
    return 1ll*C(n%Mod,m%Mod)*Lucas(n/Mod,m/Mod)%Mod;
}
inline int Get(const int a,const int b){
    return Lucas(a+b,a);
}
int r1,r2,c1,c2;
int main(){
    scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
    r1++;c1++;r2++;c2++;
    printf("%d\n",(((Get(r2,c2)+Get(r1-1,c1-1))%Mod-(Get(r1-1,c2)+Get(r2,c1-1)%Mod))%Mod+Mod)%Mod);
    return 0;
}