[POI2008]Uci

给一个 $n\times m$ 的地图，计算从 $(n,1)$（即左下角）走到第 $x$ 列第 $y$ 行的路径条数对 $k$ 取模的结果。

走过的点不能再走，且转弯时只能向右转。

输入格式

第一行输入三个整数 $n$、$m$、$k$。

第二行输入两个整数 $x$、$y$，注意这里 $x$ 是列号、$y$ 是行号。

以下 $n$ 行，每行 $m$ 个字符描述地图：+ 表示可以走，* 表示障碍。

输出格式

一行一个整数，即路径条数对 $k$ 取模的结果。

样例输入

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

样例输出

2

数据范围

• $1\le n, m\le 100$；
• $1\le k\le 10^9$。

来源与许可

本题为 POI 2008 试题「Uci」，题面与测试数据整理自 BZOJ 1126。

样例 1

输入

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

输出

2