D. Мета-cет
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы любите настольную карточную игру «Сет». Каждая карта содержит $$$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$$$) — характеристики карты. Гарантируется, что все карты различны.

Выходные данные

Выведите одно число — количество мета-сетов.

Примеры
Входные данные
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
Входные данные
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
Выходные данные
3
Входные данные
9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Выходные данные
54
Входные данные
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
Выходные данные
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$$$ мета-сета.