**Meta-set solution codeforces** – You like the card board game “Set”. Each card contains 𝑘k features, each of which is equal to a value from the set {0,1,2}{0,1,2}. The deck contains all possible variants of cards, that is, there are 3𝑘3k different cards in total.

A feature for three cards is called good if it is the same for these cards or pairwise distinct. Three cards are called a set if all 𝑘k features are good for them.

For example, the cards (0,0,0)(0,0,0), (0,2,1)(0,2,1), and (0,1,2)(0,1,2) form a set, but the cards (0,2,2)(0,2,2), (2,1,2)(2,1,2), and (1,2,0)(1,2,0) do not, as, for example, the last feature is not good.

A group of five cards is called a meta-set, if there is strictly more than one set among them. How many meta-sets there are among given 𝑛n distinct cards?

## [Solution] Meta-set solution codeforces

The first line of the input contains two integers 𝑛n and 𝑘k (1≤𝑛≤1031≤n≤103, 1≤𝑘≤201≤k≤20) — the number of cards on a table and the number of card features. The description of the cards follows in the next 𝑛n lines.

Each line describing a card contains 𝑘k integers 𝑐𝑖,1,𝑐𝑖,2,…,𝑐𝑖,𝑘ci,1,ci,2,…,ci,k (0≤𝑐𝑖,𝑗≤20≤ci,j≤2) — card features. It is guaranteed that all cards are distinct.

Output one integer — the number of meta-sets.

input

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

## [Solution] Meta-set solution codeforces

1

input

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

## [Solution] Meta-set solution codeforces

3

input

9 2 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2

## [Solution] Meta-set solution codeforces

54

input

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

output

0

## [Solution] Meta-set solution codeforces

Let’s draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: 11, 22, 33. The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid.

You can see the first three tests below. For the first two tests, the meta-sets are highlighted.

In the first test, the only meta-set is the five cards (0000, 0001, 0002, 0010, 0020)(0000, 0001, 0002, 0010, 0020). The sets in it are the triples (0000, 0001, 0002)(0000, 0001, 0002) and (0000, 0010, 0020)(0000, 0010, 0020). Also, a set is the triple (0100, 1000, 2200)(0100, 1000, 2200) which does not belong to any meta-set.

## [Solution] Meta-set solution codeforces

In the second test, the following groups of five cards are meta-sets: (0000, 0001, 0002, 0010, 0020)(0000, 0001, 0002, 0010, 0020), (0000, 0001, 0002, 0100, 0200)(0000, 0001, 0002, 0100, 0200), (0000, 0010, 0020, 0100, 0200)(0000, 0010, 0020, 0100, 0200).