题目描述

在$\red {m\times n}$的主格中任意指定$\red {x}$个格子构成一个棋盘，在任一个构成的棋盘上放置$\red {k}$个棋子，要求任意两个棋子不得位于同一行或同一列上，要求输出满足条件的所有方案。（注意棋盘是稀疏的，即$\red {x<m\times n/2,1<m,n<10}$）

1、对给定棋盘，求出该棋盘可放置的最多的棋子数$\red {p}$；

2、记$\red {d_i~}$为该盘上放置$\red {I}$个棋子时的方案总数$\red {(1<=i<=p)}$，其中经旋转和镜面反射而得的方案记为不同的方案，对于每一个$\red {i}$，求出相应的$\red {d _i~}$ 。

3、程序应能够连续处理多个棋盘，对每一个棋盘，输出$\red {p}$和$\red {d_1,d_2,…d_p}$,，只需输出数字，不必输出具体的方案。

输入格式

第一行是两个数字，代表第一个棋盘的$\red {m}$和$\red {n}$，以下为一个仅由$\red {0}$和$\red {1}$组成的$\red {m\times n}$矩阵，某一个位置为$\red {1}$表示相应的格子在这个棋盘，为$\red {0}$表示相应的格子不在棋盘上。

输出格式

第一行为棋盘可放置的最多的棋子数$\red {p}$；第二行分别列出从放$\red {1}$个棋子数到放$\red {p}$个棋子的方案总数。

样例

输入样例

5 5

0 1 1 1 0

0 1 0 0 0

1 1 1 0 0

0 0 1 0 0

0 0 1 1 0

输出样例

The maxnumber=4

1:10

2:28

3:24

4:5