该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

刘学习的仓鼠是一只自由而勇敢的仓鼠。虽然天气预报说今天会打雷，它依然坚强地外出觅食。现在觅食结束了，仓鼠希望带着食物尽快且安全地回家。

Description

已知从出发处到家里的路可以看成是一个矩形，该矩形可划分为n×m个区域。仓鼠处在(1,1)的位置，而家在(n,m)。仓鼠每次可以移动到当前区域的上下左右四个相邻区域之一。已知有一些区域可以导电。如果雷电劈在一个导电的区域，电流将瞬间传播到所有与它连通的导电区域(一个区域和它上下左右四个区域连通。注意是导电区域，非导电区域就算连通也不会受影响)。仓鼠不能移动到一个有电流的区域。假设仓鼠每移动一次需要1秒，它希望能在n+m-2秒内到家。假设初始时间为第0秒。请计算仓鼠有多少种不同的回家路线。因为答案可能很大，所以只需计算其mod 100000001后的值。

Format

Input

第一行两个整数n和m，表示路可划分为n×m个区域。3<=N,M<=1000。
接下来n行，每行m个数，用来描述各个区域的导电情况。1表示导电，0不导电。左上角为出发位置(1,1)，右下角为家（n,m）。
接下来n+m-2行每行两个整数x y，其中的第i行表示第i秒雷电劈到的位置为(x,y)。1<=X<=N， 1<=Y<=M。

Output

一个整数，表示路线数mod 100000001后的值。

Sample 1

Input

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

Output

2

Limitation

1s, 68096KiB for each test case.

Hint

样例解释：
方案一： (1,1)-->(2,1)-->(2,2)-->(2,3)-->(3,3)
方案二： (1,1)-->(2,1)-->(2,2)-->(3,2)-->(3,3)
对40%的数据 3<=N,M<=100。

Source

Unknown