题目描述

一个n*m的网格系统。其中一些格子是障碍物，另一些是空的。(1,1)是左上 角，(n,m)是右下角（这两个格子都是空的）。你需要在这个网格系统中铺设管道 使得水能从(1,1)经过管道流到(n,m)，即使得(1,1)和(n,m)通过管道连通。 管道不能经过障碍物。每个不是障碍的格子必须经过一次且仅一次，并且在管 道经过的每个格子只能是上下，上左，上右，左右，左下，右下六种连接情况。不 能存在无用的管道。 求方案数目（模10007）。

输入格式

输出格式

3 3 
... 
... 
... 

12

提示

2<=N, M<=10

题目来源

没有写明来源