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

class Main {

	private static final int M = 1000000007;

	private static Combination c;

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int r1 = sc.nextInt();
		int c1 = sc.nextInt();
		int r2 = sc.nextInt();
		int c2 = sc.nextInt();

		c = new Combination(r2 + c2 + 10, M);
		long answer = f(r2 + 1, c2 + 1);
		answer = (((answer - f(r2 + 1, c1)) % M) + M) % M;
		answer = (((answer - f(r1, c2 + 1)) % M) + M) % M;
		answer = (answer + f(r1, c1)) % M;
		System.out.println(answer);
	}

	private static long f(int a, int b) {
		return c.choose(a + b, a);
	}

	private static class Combination {
		private final int M;
		private long[] fact;
		private long[] ifact;
		private long[] inv;

		public Combination(int n, int M) {
			this.M = M;
			fact = new long[n + 1];
			ifact = new long[n + 1];
			inv = new long[n + 1];

			fact[0] = fact[1] = 1;
			ifact[0] = ifact[1] = 1;
			inv[1] = 1;

			for (int i = 2; i <= n; i++) {
				fact[i] = fact[i - 1] * i % M;
				// p = (p / a * a) + (p % a)
				// 0 ≡ (p / a * a) + (p % a)          (mod p)
				// a^(-1) ≡ - (p % a)^(-1) * (p / a)  (mod p)
				inv[i] = M - inv[M % i] * (M / i) % M;
				ifact[i] = ifact[i - 1] * inv[i] % M;
			}
		}

		public long choose(int n, int k) {
			if (n < k) return 0;
			if (n < 0 || k < 0) return 0;
			return fact[n] * (ifact[k] * ifact[n - k] % M) % M;
		}
	}

}
