UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1849. 和谐庆典

统计 下载数据

Description

一年一度的HXOI结束了,主办方决定举办一次游行以庆祝这一次活动的圆满完成。 举办地设在了YL City,YL City可以看做一个N×M的矩阵,以左上角为坐标原点,从上至下为X轴正方向,从左至右为Y轴正方向,这样YL City的每一个位置都可以由一个数对(x,y)来表示(1≤x≤N,1≤y≤M)。 一开始所有志愿者在入口集合,然后每一个志愿者沿着不同的路线行进,最后在终点汇合。当然,为了使游行更加完美,每一条从起点到终点的路线都必须有志愿者负责。由于时间紧迫,考虑到过于复杂的路线会使得志愿者出错,因此主办方对游行的路线作了如下规定,从起点开始,志愿者要么直走,要么向右走,并且不能经过相同的地方。 现在主办方已经决定将游行的出发点设在(N+1,1),而终点设在(X0,Y0),而你负责计算这次游行需要多少志愿者的参与。

Input

第一行有三个正整数N,M,K。 第二行有两个正整数Y0,X0 第三~N+2行,每行M个字符,如果第(i+2)行,第j个字符是+,表示(i,j)可以通过,否则表示(i,j)不能通过(池塘,WC等等..)。

Output

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

Sample Input


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

Sample Output

2

Hint

在30%的数据中,N,M < =20
在100%的数据中,N,M < = 100,K < = 10^9

Source