The Great Escape

Al Bytone, a notorious thief, is planning to rob a bank. He knows all too well that the moment he robs it, a pursuit begins. Unfortunately Al Bytone is a poor driver, and turning left gives him great trouble, so he wants an escape route on which, at every intersection, he only drives straight ahead or turns right. He also knows that once he passes through an intersection, the police move in and wait there, so he may pass through any intersection at most once. On top of that, some intersections already have police, and he must avoid those as well. (There is no police at the intersections near the bank or near the hideout.)

The streets of Byteburg form a rectangular grid. Every street runs either North-South or East-West, and every two streets of different orientation meet at exactly one intersection. The bank lies just south of the south-westernmost intersection, and Al Bytone starts his escape driving North.

Write a program that:

• reads the location of the hideout, the intersections that have police, and a positive integer $k$;
• computes the number of distinct escape routes from the bank to the hideout that obey the rules above;
• prints that number modulo $k$.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 100$, $1 \le k \le 10^9$). Here $n$ is the number of East-West streets and $m$ is the number of North-South streets.

The second line contains two integers $x$ and $y$ ($1 \le x \le m$, $1 \le y \le n$): the hideout is at the intersection of the $x$-th North-South street and the $y$-th East-West street. North-South streets are numbered $1$ to $m$ from West to East, and East-West streets are numbered $1$ to $n$ from North to South.

Each of the next $n$ lines contains $m$ characters, each either * or +. The character in line $i$, column $j$ describes the intersection of the $i$-th East-West street with the $j$-th North-South street: * means there is police at that intersection, and + means it is free and the route may pass through it.

Al Bytone drives onto the intersection with coordinates $(1, n)$ from the South, that is, from the nonexistent intersection $(1, n+1)$. Coordinates are written as (North-South street number, East-West street number).

Print, in a single line, the number of valid escape routes taken modulo $k$.