2821: 打雷了

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:外部导入
提交:0 解决:

题目描述

某天,你被放在了一个可以划分成N*M个区域的矩形平原上。一开始你的位置在(11),出口在(NM)。现在老天要开始打雷了。每秒钟将会有一道雷劈在(XY)的区域,你要是处于这个位置,后果……。更糟糕的是现在平原上有一些区域是导电的。如果雷电劈在一个导电的区域,电流将瞬间传播到所有与它连通的导电区域(一个区域和它上下左右四个区域连通。注意是导电区域,非导电区域就算连通也不会受影响),这些电流流经的区域你肯定都不能走了。现在时间紧迫,你每秒只能向上下左右4个方向移动一个区域,而且你要在最短的时间内走出平原(即用N+M-2秒)的时间。请你算出一共有多少种路线能够走到出口,方案可能比较多,你只需输出方案数MOD 100000001的值,如果你不能走到出口,则输出“Poor Y!”(不含引号);

输入

第一行2个整数 N,M

接下来N行每行M个数 描述这个平原 1表示该区域是导电区域,0表示不是。

接下来N+M-2行每行2个整数X,Y  表示1~N+M-2秒内每秒雷电劈下的坐标。

输出

输出一行  一个整数表示总方案MOD 100000001后的值     如果你不能走到出口则输出“Poor Y!”(不含引号)。

样例输入 复制

3 3
0 0 1
1 0 0
1 0 0
1 2
2 1
1 3
2 2

样例输出 复制

2

提示

40%的数据 3<=N,M<=100

100% 的数据 3<=N,M<=1000

1<=X<=N;

1<=Y<=M;