3228. 千反田和折木奉太郎

千反田和折木奉太郎升入大学了。千反田同学为了更好的支持家族事业，努力学习理科知识。一日，他们在上完数学课后，发现了一道有趣的课后习题。

所有长度为 $n$ 的 01 序列，如果可以任意交换位置得到另外一个，我们认为是一类的，问本质不同有多少类？

这当然难不倒我们的千反田大小姐，长度为 $n$ 的 01 序列，如果包含 $k$ 个 1，那么凡是包含 $k$ 个 1 的序列本质都是相同的（因为可以任意交换嘛）, 所以答案是 $n+1$。

这时候，折木同学就说：我们可以拓展这类问题，想想 $2 \times n$ 的 01 矩阵，可以任意交换两列，这个时候结果呢？

千反田瞪大了眼睛，说道：我很好奇！

折木同学开始解释了：我们可以同 Burnside 引理，考虑长度为 3 的 01 序列，一共有 8 种可能，交换方式一共 $3! = 6$ 种：

• 对于 (1, 2, 3) 不动点个数是 8 个；
• 对于 (1, 3, 2) 不动点个数是 4 个；
• 对于 (2, 1, 3) 不动点个数是 4 个；
• 对于 (2, 3, 1) 不动点个数是 2 个；
• 对于 (3, 1, 2) 不动点个数是 2 个；
• 对于 (3, 2, 1) 不动点个数是 4 个；

那么 $(8 + 4 + 4 + 2 + 2 + 4) \div 6 = 24 \div 6 = 4$。 是不是很奇妙？

好了那么给你个练习，给定 $n \times m$ 的 01 矩阵，可以交换任意两行两列，可以交换达到的矩阵认为是同一类，那么本质不同的有多少类呢？

千反田同学虽然学习了 Burnside，但是还是感觉迷迷糊糊的，你能否帮助她呢？