UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3187. [Coci2011]Voda

Statistics 下载数据

Description

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

Input

Output

Sample Input

3 3
...
...
...

Sample Output

12

Hint

2<=N, M<=10

Source