Fişierul intrare/ieşire:	manhattan.in, manhattan.out	Sursă	Lot 2017 Baraj 1
Autor	Zoltan Szabo	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.15 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Manhattan

Î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.

Cunoscând două zone Z1 şi Z2 ce nu se intersectează în nici un punct, să se calculeze numărul traseelor distincte modulo 666013 care pornesc din zona Z1 şi se termină în zona Z2.

Pentru zonele Z1 şi Z2 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

• Coordonatele zonelor sunt numere naturale mai mici sau egale cu 100 000.
• Pentru teste în valoare de 10 puncte coordonatele zonelor sunt mai mici sau egale cu 30.
• Pentru teste în valoare de 30 puncte coordonatele zonelor sunt mai mici sau egale cu 300.
• Pentru teste în valoare de 50 puncte coordonatele zonelor sunt mai mici sau egale cu 1000.
• Pentru teste în valoare de 50 de puncte proiecţiile pe axele Ox şi Oy ale zonelor sunt disjuncte.

Exemplu

Cum se trimit solutii?