说明

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

输入格式

第一行是两个数字m，n

第二行到第m+1行，每行有n个0或1组成的字符序列，字符间用一个空格分隔，为1表示相应的格子在棋盘上，为0表示相应的格子不在棋盘上。

输出格式

第一行是棋盘可放置的最多的棋子数目。

第二行分别列出从放1个棋子到放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