Description

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

Input

Output

Sample Input

Sample Output

Hint

2<=N, M<=10

Source