臭名昭著的窃贼 Al Bytone 计划抢劫银行。他非常清楚，一旦他抢劫了银行，追捕就会随之开始。不幸的是，Al Bytone 的驾驶技术很差，左转对他来说非常困难。因此，他试图设计一条逃跑路线，使得在每个路口他要么直行，要么右转。他还意识到，一旦他经过任何一个路口，警察就会赶到并留在那里守候。因此，他经过任何一个路口最多只能一次。此外，警察总是出现在某些特定的路口，所以 Al Bytone 也必须避开这些路口（银行附近和 Al Bytone 藏身处附近的路口没有警察）。

Al Bytone 正在规划他的逃跑路线。令你感到非常（且相当不愉快）惊讶的是，他拜访了你，并要求你计算出从银行到他藏身处、且满足上述所有要求的不同逃跑路线的数量。不用说，Al Bytone 不接受“不”作为回答……

Byteburg 的街道构成了一个矩形网格。每条街道要么是南北走向，要么是东西走向，且每两条非平行街道都会相交。银行位于最西南侧路口的南面。Al Bytone 将从向北行驶开始他的大逃亡。

任务

编写一个程序：

• 从标准输入读取藏身处的位置、有警察的路口的描述以及一个正整数 $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$ 条南北走向街道的交汇处。"*" 表示该路口有警察，而 "+" 表示该路口没有警察，因此逃跑路线可以经过该路口。

Al Bytone 从南面驶入坐标为 $(1, n)$ 的路口开始他的大逃亡，即从一个不存在的路口 $(1, n+1)$ 进入。

输出格式

你的程序应在标准输出的第一行（也是唯一一行）输出逃跑路线数量对 $k$ 取模后的余数。

样例

输入 1

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

输出 1

2