题目描述

题目译自 XV OI Olimpiada Informatyczna – II etap Ucieczka

拜托城街道为矩形网格，Al 从银行所在的虚拟点 $(1, n+1)$ 出发，向北进入交叉口 $(1, n)$，需逃往藏身处 $(x, y)$，路径需满足：

1. 仅允许直行或右转，禁止左转；
2. 不可重复经过任一交叉口；
3. 避开有警力巡逻的交叉口（标记为 *），仅可通行标记为 + 的交叉口（银行和藏身处所在交叉口无巡逻）。

需计算满足条件的路径总数，并输出其对 $k$ 取模的结果。

输入格式

1. 第一行：三个整数 $n, m, k$（$1 \leq n, m \leq 100$，$1 \leq k \leq 10^9$），分别表示东西向街道数、南北向街道数、模数；
2. 第二行：两个整数 $x, y$（$1 \leq x \leq m$，$1 \leq y \leq n$），表示藏身处位于第 $x$ 条南北街与第 $y$ 条东西街的交叉口；
3. 接下来 $n$ 行：每行 $m$ 个字符（* 或 +），第 $i$ 行第 $j$ 列表示第 $i$ 条东西街与第 $j$ 条南北街的交叉口状态（东西街从北向南编号 1~n，南北街从西向东编号 1~m）。

输出格式

输出一行整数，表示满足条件的路径总数对 $k$ 取模的结果。

样例

输入

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

输出

2