#3604. [Sdoi2014]电路板

所谓电路板，可以看作是一个n*m的格子图。 

用户给定的电路由若干电路原件组成，每一个电路原件可能会占用一个或多个格子。这里，我们将被电路原件占据的格子分为两类。第一类只是纯粹占据了这个格子，之后这个格子不会再被使用，也不会从被占据的位置连出去任何的电路线。这样的格子被我们视作是电路板上的障碍物。还有一类格子，我们称为是电路原件的接口，上面虽然被电路原件占用，但是仍有可能从其中连出去一些电路线到其它的电路原件上，从而形成电路。 

对于电路图中一些链接某两个原件的电路线，我们可以指定为电路板上的k个格子对，要求每对格子对之间连一条电路线。 

同一个格子可能属于多个格子对（比如一些并联电路）。 

任意两条电路线不能相交（但可以连接到同一个有着电路原件的格子中），且电路板上的每一个格子的每一条边都只能经过一条电路线。（所以每一个电路原件的接口上只能接出去最多4条不同的电路线）。然而，每一个不被电路原件占用的格子内却可以经过多条电路 

线。 

具体来说：为了保证电路线不相交，可以一条电路线从上边界进入当前格子，从左边界离开这个格子，另外一条电路线可以从下边界进入格子，从右边界出去。（需要注意的是：电路线本身是没有方向感念的，即格子对描述的边关系是无向边。所以这样的方案也可以描述为从左边界进入后从上边界出去，从右边界进入后从下边界出去）相似的方案还有好几种。 

现在，Alice希望找到一个可行方案，使得路径的总长度最短。而Bob则希望知道满足最短长度的方案有多少种。