Description
There are N FAKE knights in the city. In order to protect the city, you need to find two FAKE knights to protect the whole area.
There are K defending properties, two FAKE knights can protect the city perfectly if, for each property, both of them have it or none of them have 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 = [1, 3], they can protect the city perfectly.
However, if K = 5, A1 = [1, 2, 5] and A2 = [1, 4, 5], they cannot protect the city since properties 2 and 4 do not satisfy the constraint.
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 = 15
Hint 1: Think carefully before you start!
Hint 2: You can refer to these bitwise operators if you need.
Input
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
Output the number of ways you can choose to protect the city. Print a newline character at the end of the line.