시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB644100.000%

문제

In the first quadrant of the cartesian plan, we define a zone, denoted by $Z(x,y,u,v)$, as a set of lattice points which belong to a rectangle defined by to diagonally opposite points, $(x,y)$ and $(u,v)$, with $x≤u$ and $y≤v$. In particular, a zone can contain points on a single segment when $x=u$ or $y=v$. Also, it may be formed from a single point, if $x=u$ and $y=v$.

A path between two lattice points is defined as a minimal set of horizontal and vertical segments of length $1$ which join the two points.

Given two zones $Z_1​(a,b,c,d)$ and $Z_2​(e,f,g,h)$ which do not intersect in any point, compute the number of distinct paths, modulo $666\, 013$, that start in $Z_1$​ and end in $Z_2$​.

입력

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

출력

The output should containt a single number representing the number of distinct paths modulo $666\, 013$.

제한

  • $1≤a,b,c,d,e,f,g,h≤10^5$

예제 입력 1

1 1 1 2 2 2 3 2

예제 출력 1

7

예제 입력 2

1 1 2 2 2 3 3 4

예제 출력 2

53

예제 입력 3

8 4 13 7 2 3 6 8

예제 출력 3

44702

예제 입력 4

80 40 130 70 20 30 60 80

예제 출력 4

145267