There are N knights in the city. In order to protect the city, you need to find two knights to protect the whole area.
There are K defending properties, two knights can protect the city perfectly if, for each property, at least one knight has it.
For example:
we'll use A1 = [1, 3] describing that the first knight has properties 1 and 3.
If K = 3, A1 = [1, 3], and A2 = [2, 3], they can protect the city perfectly.
However, if K = 5, A1 = [1, 3, 5] and A2 = [4, 5], they cannot protect the city since none of them has the defending property 2.
Given the properties of N knights, how many ways you can select two knights such that the city can be protected perfectly?
Testcase 1 ~ 6:
1 ≤ N ≤ 103, 1 ≤ K ≤ 10
Testcase 7 ~ 8:
N = 30000, K = 30
Hint: you can use bitwise operator to handle the testcase 7 and 8!
There're two integers N and K, describing the number of knights and the number of properties.
For the next N lines, each line contains K digits (0 or 1). the k-th digit on the i-th line describes whether knight i has the property k.
Output the number of ways you can choose to protect the city. Print a newline character at the end of the line.