Liczba scieżek

Witam,
Prosiłbym o jakiegoś hint'a do takiego zadania.

Treść:
Policz liczbę ścieżek w danym prostokącie (możesz się poruszać w górę i prawo). Zaczynasz od lewego rogu a kończysz w prawym rogu. Dodatkowo w tym prostokącie występuje inny prostokąt przez który nie można poprowadzić ścieżki. (Prostokąt nie zahacza o pkt wejścia i wyjścia)

Mamy podane n, m, p. Dla m, n <= 10⁵ , p < 10⁹
x1, y1, x2, y2 <= 10⁵, gdzie określone są dwa przeciwległe pkt w prostokącie.

Wynik podaj modulo p.

#Pierwszym moim pomysłem było napisać zwykłego dynamika. Jednak jego złożoność wynosi O(nm) co jednak nie pykło.
#Drugim z pomysłów było to, że dziele sobie ten prostokąt na 9 mniejszych (krawędzie prostokąta wewnątrz definiują mi jaki jest podział) i obliczam brzegowe wartości tych prostokątów z symbolu Newtona. Jednak nadal nie wiem jak zmergować 2 takie prostokąty.

co to jest n m i p?

n, m to długość "dużego" prostokąta.
p to liczba prze która należy modulować.

Dla prostokąta bez ograniczeń możesz to policzyć w czasie stałym: masz m kroków w prawo i n kroków w dół, liczysz liczbę permutacji i gotowe.
Mając w środku prostokątną przeszkodę najpierw liczysz liczbę wszystkich ścieżek (tak jakby przeszkody nie było), a potem odejmujesz ścieżki dochodzące do górnej krawędzi przeszkody i idące w dół oraz te dochodzące do lewej krawędzi przeszkody i idące w prawo.