Description

在$M*N$的主格中任意指定X个格子构成一个棋盘，而其它格子是残缺的，不能放棋子。在任一个构成的棋盘上放置K个棋子， 要求任意两个棋子不得位于同一行或同一列上。求满足条件的所有方案数。 注意：棋盘是稀疏的，即$X＜(M*N)/2$ 编程任务：

1. 对给定的一个棋盘，求出该棋盘可放置的最多的棋子数P；
2. 该棋盘上恰好放置i个棋子时的方案总数（1≤i≤P）其中经旋转和镜面反射而得的方案记为不同的方案

Format

Input

第1行：2个整数M,N，表示棋盘的行数和列数( 1＜M，N＜10) 接下来是M行，每行N个空格分开的数字（0或者1），1表示相应的格子在棋盘上，0表示相应的格子不在棋盘上。

Output

第1行：1个整数表示可放置的最多的棋子数P 接下来P行，每行分别列出放i（1≤i≤P）个棋子时的方案总数。

Samples

5 4
0 1 1 1 
0 1 0 0 
1 1 1 0 
0 0 1 0 
0 0 1 1 

4
1:10
2:28
3:24
4:5