대탈주

악명 높은 도둑 알 바이톤(Al Bytone)이 은행을 털 계획을 세운다. 은행을 터는 순간 곧바로 추격이 시작된다는 것을 그는 잘 알고 있다. 그런데 알 바이톤은 운전이 서툴러서 좌회전을 몹시 어려워한다. 그래서 그는 모든 교차로에서 직진하거나 우회전만 하는 탈출 경로를 짜려고 한다. 또한 어떤 교차로를 한 번 지나가면 곧바로 경찰이 그곳에 배치되어 지키기 때문에, 같은 교차로는 최대 한 번만 지날 수 있다. 게다가 처음부터 경찰이 지키고 있는 교차로도 있으므로 그런 교차로 역시 피해야 한다. (은행 근처와 은신처 근처의 교차로에는 경찰이 없다.)

바이트버그(Byteburg)의 거리는 직사각형 격자를 이룬다. 모든 거리는 남북 방향 또는 동서 방향으로 뻗어 있으며, 방향이 서로 다른 두 거리는 반드시 한 교차로에서 만난다. 은행은 가장 남서쪽 교차로의 바로 남쪽에 있고, 알 바이톤은 북쪽을 향해 출발한다.

다음을 수행하는 프로그램을 작성하라.

• 은신처의 위치, 경찰이 있는 교차로들, 그리고 양의 정수 $k$를 입력받는다.
• 위 규칙을 모두 만족하면서 은행에서 은신처로 가는 서로 다른 탈출 경로의 개수를 구한다.
• 그 개수를 $k$로 나눈 나머지를 출력한다.

첫째 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n, m \le 100$, $1 \le k \le 10^9$). $n$은 동서 방향 거리의 수, $m$은 남북 방향 거리의 수이다.

둘째 줄에 두 정수 $x$와 $y$가 주어진다 ($1 \le x \le m$, $1 \le y \le n$). 은신처는 $x$번째 남북 방향 거리와 $y$번째 동서 방향 거리가 만나는 교차로에 있다. 남북 방향 거리는 서쪽에서 동쪽으로 $1$부터 $m$까지, 동서 방향 거리는 북쪽에서 남쪽으로 $1$부터 $n$까지 번호가 매겨진다.

이어지는 $n$개의 줄에는 각각 * 또는 + 문자가 $m$개씩 주어진다. $i$번째 줄 $j$번째 문자는 $i$번째 동서 방향 거리와 $j$번째 남북 방향 거리가 만나는 교차로를 나타낸다. *는 그 교차로에 경찰이 있음을, +는 경찰이 없어 지나갈 수 있음을 뜻한다.

알 바이톤은 좌표 $(1, n)$의 교차로로 남쪽에서, 즉 존재하지 않는 교차로 $(1, n+1)$에서 진입하여 출발한다. 여기서 좌표는 (남북 방향 거리 번호, 동서 방향 거리 번호) 순서이다.

탈출 경로의 개수를 $k$로 나눈 나머지를 한 줄에 출력한다.