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
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    final long mod = 1000000000+7;
    long[] fac, inv;

    public static void main(String[] args) {
        Main main = new Main();
//        main.solve();
//        out.flush();
        System.out.println(main.solve());
    }
    // segment tree to record minimum value
    // Each point has a infinite distance from 0 (except itself)
    long solve() {
        Scanner sc = new Scanner(System.in);
        int r1 = sc.nextInt(), c1 = sc.nextInt(), r2 =sc.nextInt(), c2 = sc.nextInt();
        initial(r2+c2+5);
        long ans = helper(r2,c2);
        ans -= helper(r2, c1-1);
        ans -= helper(r1-1,c2);
        ans += helper(r1-1,c1-1);
        ans = (ans+10*mod)%mod;
        return ans;
    }
    long helper(int r, int c){
        if(r==0) return c+1;
        if(c==0) return r+1;
        if(r>c){
            int mid = r;
            r = c; c = mid;
        }
        // let r <= c
        long ans = 0;
        for(int row = r; row >=0; row--){
            long cur = fac[row+c+1]*inv[c]%mod*inv[row+1]%mod;
            ans = (ans+cur)%mod;
        }
        return ans;
    }
    long power(long base, long p){
        long ans = 1;
        while(p>0){
            if(p%2==1) ans = ans*base%mod;
            base = base*base%mod;
            p /= 2;
        }
        return ans;
    }
    void initial(int maxN){
        fac = new long[maxN+1];
        inv = new long[maxN+1];
        fac[0] = 1;
        for(int i=1;i<=maxN; i++) fac[i] = i*fac[i-1]%mod;
        inv[maxN] = power(fac[maxN], mod-2);
        inv[0] = 1;
        for(int i=maxN-1;i>0;i--){
            inv[i] = inv[i+1]*(i+1)%mod;
        }
    }
    // compute nCm

}

