你喜欢纸牌游戏“Set”。每张卡包含 $$$k$$$ 个特征,每个特征都等于集合 $$$\{0, 1, 2\}$$$ 中的一个值。这副牌包含所有可能的牌变体,即总共有 $$$3^k$$$ 种不同的牌。
如果三张牌的特征相同或成对不同,则该特征被称为良好。如果所有 $$$k$$$ 功能都适合三张卡,则将三张卡称为一组。
例如,卡片 $$$(0, 0, 0)$$$、$$$(0, 2, 1)$$$ 和 $$$(0, 1, 2)$$$ 构成一组,但卡片 $$$(0, 2, 2)$$$、$$$(2, 1, 2)$$$ 和 $$$(1, 2, 0)$$$ 不,例如,最后一个功能不好。
一组五张牌被称为元集,如果其中有严格多于一组的话。给定的 $$$n$$$ 不同卡中有多少个元集?
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le 20$$$) — 桌子上的牌数和牌特征的数量。接下来的 $$$n$$$ 行是卡片的描述。
描述卡片的每一行包含 $$$k$$$ 整数 $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, k}$$$ ($$$0 \le c_{i, j} \le 2$$$) — 卡片特征。保证所有卡都是不同的。
输出
输出一个整数——元集的数量。
示例
输入 #1
8 4 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0 1 0 0 1 0 0 0 2 2 0 0
输出 #1
1
输入 #2
7 4 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0
输出 #2
3
输入 #3
9 2 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
输出 #3
54
输入#4
20 4 0 2 0 0 0 2 2 2 0 2 2 1 0 2 0 1 1 2 2 0 1 2 1 0 1 2 2 1 1 2 0 1 1 1 2 2 1 1 0 2 1 1 2 1 1 1 1 1 2 1 2 0 2 1 1 2 2 1 2 1 2 1 1 1 0 1 1 2 0 0 1 0 2 2 0 0 2 0 0 2
输出#4
0
注意
让我们抽出表示前四个特征的卡片。第一个功能将指示卡片上的对象数量:$$$1$$$、$$$2$$$、$$$3$$$。第二个是颜色:红、绿、紫。第三是形状:椭圆形、菱形、波浪形。第四是填充:开放式、条纹式、实心式。
您可以在下面看到前三个测试。对于前两个测试,元集被突出显示。
在第一个测试中,唯一的元集是五张牌 $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$。其中的集合是三元组 $$$(0000,\ 0001,\ 0002)$$$ 和 $$$(0000,\ 0010,\ 0020)$$$。另外,集合是三元组 $$$(0100,\ 1000,\ 2200)$$$,不属于任何元集。
在第二个测试中,以下五张卡组是元集:$$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$, $$$(0000,\ 0001,\ 0002,\ 0100,\ 0200)$$$, $$$(0000,\ 0010,\ 0020,\ 0100,\ 0200)$$$。
在第三个测试中,有 $$$54$$$ 元集。