rege

Rege

== include(page="template/taskheader" task_id="rege") ==

Poveste şi cerinţă...

Se cunoaşte că regele se poate mişca pe tabla de şah doar în câmpurile învecinate pe toate cele $8$ direcţii. În figura de mai jos putem vedea deplasările posibile ale regelui la o mutare. Numim drum o succesiune de una sau mai multe astfel de mutări.
 
h2. Cerinţă
 
Cunoscând dimensiunea $M$ x $N$ a tablei de şah, respectiv poziţia iniţială (l{~1~}, c{~1~}) şi poziţia finală (l{~2~}, c{~2~}) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.

h2. Date de intrare

Fişierul de intrare $rege.in$ ...

Fişierul de intrare $rege.in$ conţine pe prima linie valorile $m$ şi $n$ separate prin spaţiu, reprezentând dimensiunile tablei  de şah, pe linia a doua numerele l{~1~} şi c{~1~} separate prin spaţiu, reprezentând linia şi coloana poziţiei iniţiale a regelui, iar pe linia a treia numerele l{~2~} şi c{~2~} separate prin spaţiu, reprezentând poziţia finală a regelui.

h2. Date de ieşire

În fişierul de ieşire $rege.out$ ...

În fişierul de ieşire $rege.out$ se va afişa pe prima linie numărul drumurilor minime distincte modulo 666013.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ M, N, l{~1~}, c{~1~}, l{~2~}, c{~2~} ≤ 1 000$

h2. Exemplu
table(example). |_. rege.in |_. rege.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 5
3 3
2 5
| 2

|
h3. Explicaţie