## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Meta-set Codeforces Solution

D. Meta-set
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You like the card board game "Set". Each card contains $k$ features, each of which is equal to a value from the set $\left\{0,1,2\right\}$. The deck contains all possible variants of cards, that is, there are ${3}^{k}$ 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 $\left(0,0,0\right)$$\left(0,2,1\right)$, and $\left(0,1,2\right)$ form a set, but the cards $\left(0,2,2\right)$$\left(2,1,2\right)$, and $\left(1,2,0\right)$ 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?

Input

The first line of the input contains two integers $n$ and $k$ ($1\le n\le {10}^{3}$$1\le k\le 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 ${c}_{i,1},{c}_{i,2},\dots ,{c}_{i,k}$ ($0\le {c}_{i,j}\le 2$) — card features. It is guaranteed that all cards are distinct.

Output

Output one integer — the number of meta-sets.

Note

Let's draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: $1$$2$$3$. 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 . The sets in it are the triples  and . Also, a set is the triple  which does not belong to any meta-set.