[Coci2011]Voda

时间限制:10s      空间限制:128MB

题目描述

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


输入格式


输出格式


样例输入

3 3 
... 
... 
... 
 

样例输出

12

提示

2<=N, M<=10


题目来源

没有写明来源