맨해튼

직교 좌표계의 제1사분면에서 $(x,y)$와 $(u,v)$를 대각선 꼭짓점으로 하는 직사각형에 속한 격자점의 집합을 구역이라고 하며, $Z(x,y,u,v)$로 표기한다. 단, $x \le u$이고 $y \le v$이다. $x=u$ 또는 $y=v$이면 구역은 한 선분 위의 점들만 포함할 수 있고, $x=u$이고 $y=v$이면 구역은 점 하나로 이루어진다.

두 격자점 사이의 경로는 두 점을 잇는 길이 1의 수평 선분과 수직 선분의 최소 집합이다.

서로 공통된 점이 없는 두 구역 $Z_1(a,b,c,d)$와 $Z_2(e,f,g,h)$가 주어진다. $Z_1$에서 출발해 $Z_2$에서 끝나는 서로 다른 경로의 수를 $666\,013$으로 나눈 나머지로 구하라.

첫 줄에 여덟 개의 정수 $a,b,c,d,e,f,g,h$가 주어진다. 이 값들은 두 구역의 경계이다.

경로의 수를 $666\,013$으로 나눈 나머지를 한 개의 정수로 출력한다.

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