Ucieczka

Limit pamięci: 64 MB

Al Bajtone, znany na całym świecie złodziej planuje napad na bank. Wie, że jak tylko obrabuje bank, rozpocznie się policyjny pościg. Al Bajtone jest niestety kiepskim kierowcą i skręcanie w lewo sprawia mu kłopoty. Chce więc tak zaplanować ucieczkę, aby przez każde skrzyżowanie przejeżdżać na wprost lub skręcać w prawo. Wie też, że jeżeli przez jakieś skrzyżowanie raz przejedzie, to policja będzie tam już na niego czyhać. Nie może więc dwa razy przejeżdżać przez to samo skrzyżowanie. Dodatkowo, na niektórych skrzyżowaniach zawsze stoją patrole policji, więc takie skrzyżowania musi omijać. (Na skrzyżowaniach przy których znajdują się bank i kryjówka nie ma patroli policji).

Al Bajtone planuje trasę ucieczki z banku do swojej kryjówki. Nieoczekiwanie złożył Ci wizytę i przedstawił "propozycję nie do odrzucenia": musisz policzyć ile jest różnych tras ucieczki prowadzących z banku do kryjówki, spełniających podane warunki.

Ulice Bajtogrodu tworzą regularną prostokątną siatkę. Wszystkie ulice prowadzą w kierunku północ-południe lub wschód-zachód, a na przecięciu każdych dwóch ulic znajduje się skrzyżowanie. Bank znajduje się na południe od skrzyżowania wysuniętego najbardziej na południowy zachód. Al Bajtone rozpocznie ucieczkę w kierunku północnym.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia położenie kryjówki, opis skrzyżowań przy których stoją patrole policji, oraz pewną dodatnią liczbę całkowitą ,
• wyznaczy liczbę wszystkich takich tras ucieczki z banku do kryjówki, które spełniają podane warunki.
• wypisze na standardowe wyjście resztę z dzielenia wyniku przez .

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i (, ). Liczby i to odpowiednio liczby ulic, które prowadzą w kierunku wschód-zachód oraz północ-południe. W drugim wierszu znajdują się dwie liczby całkowite i (, ). Reprezentują one położenie kryjówki - znajduje się ona przy skrzyżowaniu -tej ulicy prowadzącej w kierunku północ-południe i -ej ulicy prowadzącej w kierunku wschód-zachód. Ulice są numerowane z zachodu na wschód i z północy na południe, odpowiednio od 1 do i od 1 do .

W każdym z następnych wierszy znajduje się znaków "*" i/lub "+". Jest to mapa miasta. Znak w -tym wierszu i -tej kolumnie tej mapy określa skrzyżowanie -tej ulicy prowadzącej z zachodu na wschód z -tą ulicą prowadzącą z północy na południe, przy czym "*" oznacza, że na skrzyżowaniu stoi patrol policji, a "+" oznacza, że przez skrzyżowanie może prowadzić trasa ucieczki.

Al Bajtone rozpoczyna ucieczkę wjeżdżając na skrzyżowanie o współrzędnych z kierunku południowego, tj. z nieistniejącego skrzyżowania .

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu resztę z dzielenia liczby wszystkich możliwych tras ucieczki przez .

Przykład

Dla danych wejściowych:

3 5 10
4 2
+++++
++*++
++++*

poprawną odpowiedzią jest:

2

Autor zadania: Marian M. Kędzierski.