#1126. [POI2008]Uci

[POI2008]Uci

题目描述

给一个 n×mn \times m 地图,计算从 (n,1)(n,1)【注:左下角】到第 xx 列的第 yy 行的路径条数modk\bmod k,走过的点不能再走,转弯只能向右转。

输入格式

第一行输入 n,m,kn,m,k

第二行输入x,yx,y,注意这里是 xxyy 行。

以下 nnmm 列的字符矩阵 + 表示可以走,* 表示障碍。

输出格式

答案 modk\bmod k

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

数据规模与约定

1n,m100,1k1091 \leq n,m \leq 100, 1 \leq k \leq 10^9