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.
Cerinţă
Cunoscând dimensiunea m x n a tablei de şah, respectiv poziţia iniţială (l1,c1) şi poziţia finală (l2,c2) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.
Date de intrare
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 l1 şi c1 separate prin spaţiu, reprezentând linia şi coloana poziţiei iniţiale a regelui, iar pe linia a treia numerele l2 şi c2 separate prin spaţiu, reprezentând poziţia finală a regelui.
Date de ieşire
Fişierul de ieşire rege.out va conţine pe prima linie numărul drumurilor minime distincte modulo 666013.
