#1849. 和谐庆典

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

3 5 10  

4 2  

+++++  

++*++  

++++*  

样例输出

2  

数据范围与提示

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