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;

int64_t Q=1000000007;
int64_t si(int64_t x,int64_t y){
   int64_t A=x,B=y,C=1;//A,Bを入れる
  for(int64_t i=1;i<=B;i++){
    C=(C*i)%Q;
  }
  int64_t N=Q-2,a=1,b=0,c=1;
  while(N>0){
    a*=2;
    if(N%a!=0){
      N-=a/2;
      int64_t d=C;
      for(int j=0;j<b;j++){
        d=(d*d)%Q;
      }
      c=(c*d)%Q;
    }
    b++;
  }
  C=c;
  for(int i=0;i<B;i++){
    C=(C*(A-i))%Q;
  }//答はC
  return C;
}
vector<int64_t> J(2000001,1);
int64_t S(int64_t a,int64_t b){
  int A=(si(a+b-1,a)+si(a+b-1,b)-1+Q)%Q;
  return A;
}

int main(){
  for(int i=1;i<=2000000;i++){
    J[i]=J[i-1]*2;
    J[i]%=Q;
  }
  int64_t o,p,q,r;
  cin>>o>>p>>q>>r;
  q++,r++;
  int64_t Z=(2*Q+S(q,r)+S(o,p)-S(o,r)-S(p,q))%Q;
  cout<<Z<<endl;
}