rege

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 \times 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.

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

Date de ieșire

Fişierul de ieşire rege.out va conţine pe prima linie numărul drumurilor minime distincte modulo $666013$.

Restricții și precizări

• $1 < m, n, l_1, c_1, l_2, c_2 \leq 1 \ 000$

Exemplu

rege.in

5 5
3 3
2 5

rege.out

2

Explicație

1. $(3, 3) - (3, 4) - (2, 5)$
2. $(3, 3) - (2, 4) - (2, 5)$