Going from the point (*x1,y1*) to the point (*x2,y2*) in the Cartesian graph takes at least |*x1−x2*|+|*y1−y2*| steps moving unit length along the x-axis or the y-axis at a time (taxicab geometry). We now wonder, how many ways are there, to go from (*x1,y1*) to (*x2,y2*) using least steps, and **without** **crossing or touching** the line *y=x*?

**Difficulty**: Medium.

### Input

- Four integers, representing
*x1, y1, x2, y2,*respectively.

### Output

The number of ways modulo 10^9+7 to go from (*x1,y1*) to (*x2,y2*) using least steps, and without crossing or touching the line *y=x*.

### Example

Given *x1*=0, *y1*=-1 which corresponds to the point (0,-1) and *x2*=1, *y2*=0 which corresponds to (1,0) there are two ways using least steps: (0,-1)→(0,0)→(1,0) and (0,-1)→(1,-1)→(1,0). But (0,-1)→(0, 0)→(1, 0) touches (0,0) which is on the line *y=x* and therefore is invalid. Thus, the correct output should be 1.

### Solution: C++

```
#include <iostream>
#include <algorithm>
using namespace::std;
int mod=1000000007;
int const max_x=500; //max value for x1 and x2
int const max_y=500; //max value for y1 and y2
int m[max_x*2][max_y*2]={}; //memorization matrix supposing |x1|,|x2|,|y1|,|y2| <= 500
int lattice_paths(int x1, int y1, int x2, int y2, int dist){
int new_dist=abs(x1-x2)+abs(y1-y2); //euclidean distance from current point to destination
if(new_dist>dist) //not shortest path
return 0;
if(x1==y1) //touched the x=y line
return 0;
if(x1==x2 && y1==y2) //reached destination
return 1;
if(m[x1+max_x][y1+max_y]!=-1) //use memorization of previous calculated paths
return m[x1+max_y][y1+max_y];
// explore all paths
int n=0;
// (a+b)mod p = (a mod p + b mod p)mod p
n=(n%mod+lattice_paths(x1+1,y1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1-1,y1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1,y1+1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1,y1-1,x2,y2,dist-1)%mod)%mod;
if(m[x1+max_x][y1+max_x]==-1) //memorize best solution from current point
m[x1+max_y][y1+max_y]=n;
return n;
}
int main(){
int x1;
int y1;
int x2;
int y2;
cin>>x1;
cin>>y1;
cin>>x2;
cin>>y2;
std::fill(*m, *m + (max_x*2)*(max_y*2), -1); //initialize memorization matrix with -1 as default value
int min_dist=abs(x1-x2)+abs(y1-y2); //calculate initial euclidean distance to destination
int n = lattice_paths(x1,y1,x2,y2,min_dist);
cout<<n;
}
```