题目描述

一年一度的 HXOI 结束了，主办方决定举办一次游行以庆祝这一次活动的圆满完成。

举办地设在了 YL City，YL City 可以看做一个 $N\times M$ 的矩阵，以左上角为坐标原点，从上至下为 $X$ 轴正方向，从左至右为 $Y$ 轴正方向，这样 YL City 的每一个位置都可以由一个数对 $(x,y)$ 来表示。

一开始所有志愿者在入口集合，然后每一个志愿者沿着不同的路线行进，最后在终点汇合。当然，为了使游行更加完美，每一条从起点到终点的路线都必须有志愿者负责。由于时间紧迫,考虑到过于复杂的路线会使得志愿者出错，因此主办方对游行的路线作了如下规定：从起点开始，志愿者要么直走，要么向右走，并且不能经过相同的地方。

现在主办方已经决定将游行的出发点设在 $(N+1,1)$，而终点设在 $(X_0,Y_0)$，而你负责计算这次游行需要多少志愿者的参与。

输入格式

第一行有三个正整数 $N,M,K$。

第二行有两个正整数 $Y_0,X_0$。

第三到 $N+2$ 行，每行 $M$ 个字符,如果第 $i+2$ 行第 $j$ 个字符是 '+'，表示 $(i,j)$ 可以通过，否则表示 $(i,j)$ 不能通过。

输出格式

由于答案可能很大，你只需输出答案模 $K$ 后的结果。

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

2

数据规模与约定

在 $30\%$ 的数据中，$N,M\le 20$。

在 $100\%$ 的数据中，$N,M\le 100$，$K\le 10^9$。