[POI2008]Uci

时间限制:20s      空间限制:162MB

题目描述

给一个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


题目来源

没有写明来源