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 <iostream>
#include <vector>
using namespace std;

static const int mod = 1000000007;

static vector<int> f, g;

int fast_power(int a, int b) {
  long long p = 1, q = a;
  while (b) {
    if (b & 1)
      p = p * q % mod;
    q = q * q % mod;
    b >>= 1;
  }
  return p;
}

void factorial(int n) {
  f.push_back(1);
  g.push_back(1);
  for (int i = 1; i <= n; i++) {
    f.push_back(1LL * f[i - 1] * i % mod);
    g.push_back(fast_power(f[i], mod - 2));
  }
}

long long h(int r, int c) {
  if (r > c) swap(r, c);

  long long res = 0;
  for (int i = 1; i <= r + 1; i++)
    res = (res + 1LL * f[c + i] * g[i] % mod * g[c] % mod) % mod;
  return res;
}

int main() {
  int r1, c1, r2, c2;
  scanf("%d %d %d %d", &r1, &c1, &r2, &c2);

  factorial(r2 + c2 + 1);
  int ans = (h(r2, c2) - h(r2, c1 - 1) - h(r1 - 1, c2) + h(r1 - 1, c1 - 1) + mod * 2) % mod;
  printf("%d\n", ans);

  return 0;
}