题目描述

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

名震天下的窃贼 Al Bajtone 计划抢劫银行。他深知一旦得手，警方将展开追捕。Al 驾驶技术欠佳，左转尤为困难，因此希望规划逃亡路径，仅直行或右转。他还知道，若某交叉口被他经过一次，警方将设伏，故不可重复经过。此外，部分交叉口常驻警力巡逻，需避开（银行和藏身处所在交叉口无巡逻）。

Al 需从银行逃至藏身处。他突访你，抛出「无法拒绝的提议」：计算满足条件的所有逃亡路径数量。拜托城的街道形成规整矩形网格，沿南北或东西方向，每两街交汇为交叉口。银行位于最西南交叉口 $(1,n)$ 南侧，Al 将从南向北启动逃亡。

编写程序：

• 从标准输入读取藏身处位置、巡逻交叉口描述及正整数 $k$。
• 计算从银行到藏身处满足条件的所有逃亡路径数量。
• 输出路径总数除以 $k$ 的余数。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n, m \leq 100, 1 \leq k \leq 10^9)$，分别表示东西向和南北向街道数及模数。第二行包含两个整数 $x, y$ $(1 \leq x \leq m, 1 \leq y \leq n)$，表示藏身处位于第 $x$ 条南北街与第 $y$ 条东西街的交叉口。街道从西向东、从北向南编号，分别为 $1$ 至 $m$ 和 $1$ 至 $n$。

接下来的 $n$ 行，每行 $m$ 个字符 * 或 +，构成城市地图。第 $i$ 行第 $j$ 列字符表示第 $i$ 条东西街与第 $j$ 条南北街交叉口的状态：* 表示有警力巡逻，+ 表示可通行。Al 从南进入交叉口 $(1,n)$，即从虚拟点 $(1,n+1)$ 北上。

输出格式

输出一行，包含一个整数，表示所有逃亡路径总数除以 $k$ 的余数。

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

2