#1126. [POI2008]Uci

题目描述

给一个n*m地图，计算从(n,1)【注：左下角】到第x列的第y行的路径条数mod k，走过的点不能再走，转弯只能向右转。

输入格式

第一行输入n m k 第二行输入x y,注意这里是x列Y行以下n行m行的字符矩阵 +表示可以走，*表示障碍。

输出格式

答案 mod k

样例

样例输入

3  5  10   

4  2   

+++++   

++*++   

++++*   

样例输出

2 

数据范围与提示

1<=N,M<=100 && 1<=K<=1e9