随着社会的不断发展，越来越多的人们意识到皇后在国际象棋里的地位应该降低，这样国际象棋才会更公平，更有意思。
在传统的棋盘上，皇后能在任意的方向 (横，竖，斜) 上移动任意的步数。
新的国际象棋规定，皇后在竖直方向上还是可以移动任意的步数， 但在除此之外的其他方向上（水平 和 对角），她只能像国王一样移动一格。
但皇后们并不罢休，即使他们被剥夺了的某些权利，她们也要想办法联合起来，即每个皇后都能被同伴支援保护。
在每个棋盘上，我们在每一列上放一个皇后。
正如前面所说，棋盘上所有的皇后都想要联合起来，也就是说，每两个相邻列的皇后之间的行距离最多只能差一格，这样才可以及时互相支援 (下图给出了四个例子，前三个是正确的，最后一个是错误的)。
现在我们给出棋盘的大小和初始状态，你能计算出一共有多少种不同的放置皇后的方法使得所有的皇后都能联合起来吗?
