Manhattan

Time limit1sMemory limit1024 MB

Summary

Count the distinct lattice paths that start in zone Z1 and end in zone Z2 for two non-overlapping rectangles, modulo 666013.

Level: Medium7 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Statement

In the first quadrant of the Cartesian plane, a zone, denoted $Z(x,y,u,v)$ , is the set of lattice points in the rectangle with diagonally opposite corners $(x,y)$ and $(u,v)$ , where $x \le u$ and $y \le v$ . A zone can lie on a single segment when $x=u$ or $y=v$ , and it is a single point when $x=u$ and $y=v$ .

A path between two lattice points is a minimal set of horizontal and vertical unit segments that join the two points.

Given two zones $Z_1(a,b,c,d)$ and $Z_2(e,f,g,h)$ that share no point, count the distinct paths that start in $Z_1$ and end in $Z_2$ , modulo $666\,013$ .

Input

The first line contains eight integers $a,b,c,d,e,f,g,h$ , the boundaries of the two zones.

Output

Print a single integer, the number of paths modulo $666\,013$ .

Constraints

$1 \le a,b,c,d,e,f,g,h \le 10^5$

Examples4

Example 1
Input
```
1 1 1 2 2 2 3 2
```
Expected output
```
7
```
Example 2
Input
```
1 1 2 2 2 3 3 4
```
Expected output
```
53
```
Example 3
Input
```
8 4 13 7 2 3 6 8
```
Expected output
```
44702
```
Example 4
Input
```
80 40 130 70 20 30 60 80
```
Expected output
```
145267
```