Вы любите настольную карточную игру «Сет». Каждая карта содержит \(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\) различных карт?
Выходные данные
Выведите одно число — количество мета-сетов.
Примечание
Будем изображать карты из примеров, указывая первые четыре характеристики. Первая характеристика будет обозначать количество объектов на карте: \(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\) мета-сета.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
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
|
3
|
|
3
|
9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
|
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
|
0
|