1248. 取暖管道

【题目描述】

一块矩形土地被分为N*M的单位正方形,现在要在这块土地埋设取暖管道,管道将从坐标为(1,1)小块(左上角,上部边缘)延伸到(N,M)(右下角,右部边缘). 共有4种管道可选,如图所示。

每种管道将占据一个单位正方形土地.而且管道不能旋转.显而易见,要构成一个管道系统,我们必须保证管道是连续贯通的.一开始,在地图上标出了已经埋设好的管道.在铺设管道系统时可以利用这些管道,但不能把它们移开铺设新管道;同时,标有树木的方格表示这里是花园,地下不能埋设管道.下图表示一个4*5的地区,(4,2)处有一个花园。

有三种不同的铺设方法,如图: 

下面请你写一个程序,对一个给定的地图,找出有多少种不同的铺设方案。

【输入格式】

第一行为两个整数N和M,接下来的M行,每行有N个整数,表示地图中的每一小格.其中1-4依次表示图中四种管道,5表示花园,0表示空地。

【输出格式】

单个整数,表示不同方法数.由于数据可能很大，只需要输出方法数Mod 99999999的结果。

【样例输入】

4 5
0 0 3 2
0 4 0 5
4 0 0 0
4 0 1 0
0 3 0 0

【样例输出】

3

【提示】

【数据规模】

1 ≤ N,M ≤ 2000

【来源】

这是一道上世纪(20世纪)的老题。。。测试数据来自makazeu@gmail.com