În primul cadran al sistemului cartezian se definește o zonă notată cu Z(x, y, u, v) , ca o mulțime de puncte laticeale ce aparțin unui dreptunghi definit prin două puncte diagonal opuse (x, y) și (u, v) cu x ≤ u și y ≤ v . În caz particular o zonă poate să conțină punctele de pe un segment când x = u sau y = v. De asemenea o zonă poate fi formată dintr-un singur punct când x = u și y = v.
Un traseu dintre două puncte laticeale se definește ca un număr minim de segmente de lungime 1 orizontale sau verticale, ce unesc cele două puncte.
Cerință
Cunoscând două zone Z1(a, b, c, d) și Z2(e, f, g, h) ce nu se intersectează în niciun punct, să se calculeze numărul traseelor distincte modulo 666013 care pornesc din zona Z1 și se termină în zona Z2.
Exemplu
Pentru zonele Z1(1, 1, 1, 2) și Z2(2, 2, 3, 2) avem 7 trasee distincte.
Date de intrare
Fișierul de intrare manhattan.in conține pe prima linie opt numere naturale a, b, c, d, e, f, g, h cu semnificațiile de mai sus.
Date de ieșire
Fișierul manhattan.out va conține pe prima linie numărul traseelor distincte modulo 666013.
Restricţii şi precizări
- Coordonatele zonelor sunt numere naturale mai mici sau egale cu
100 000. - Pentru teste în valoare de
10puncte coordonatele zonelor sunt mai mici sau egale cu30. - Pentru teste în valoare de
30puncte coordonatele zonelor sunt mai mici sau egale cu300. - Pentru teste în valoare de
50puncte coordonatele zonelor sunt mai mici sau egale cu1 000. - Pentru teste în valoare de
50de puncte proiecţiile pe axele Ox şi Oy ale zonelor sunt disjuncte.
Exemple
manhattan.in
1 1 1 2 2 2 3 2
manhattan.out
7
manhattan.in
1 1 2 2 2 3 3 4
manhattan.out
53
manhattan.in
8 4 13 7 2 3 6 8
manhattan.out
44702
manhattan.in
80 40 130 70 20 30 60 80
manhattan.out
145267
Explicații
Pentru primul exemplu: studiați exemplul de mai sus
Pentru al doilea exemplu: numărul traseelor distincte este 53
Pentru al treilea exemplu: numărul traseelor distincte modulo 666013 este 44702
Pentru ultimul exemplu: numărul traseelor distincte modulo 666013 este 145267