404350: GYM101484 K Counting Good Teams

When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph problems and bad at geometry problems with someone who is good at geometry problems but bad at graph problems.

GEMA is a programming competition study group with N members. GEMA coaches are interested in counting the number of different good teams that can be created. A good team is composed of 2 members and each member is good at at least one topic that his teammate isn't good at. Two teams are considered different if at least one member is present in one team but not in the other.

GEMA coaches are only considering the M most important topics, and they know, for each member, which topics they are good at, and which topics they are bad at.

The first line of the input contains two integers N (2 ≤ N ≤ 10⁵) and M (2 ≤ M ≤ 21), indicating respectively the number of members in the study group and the number of topics that are being considered.

The second line contains N integers. The i-th integer corresponds to x_i (0 ≤ x_i < 2^M). The j-th least significant digit of the binary representation of x_i is 1 if the i-th member is good at the j-th topic and 0 otherwise. For instance, if M = 5 and the i-th member has x_i = 11 = (01011)₂, it means that he is good at the first, second and fourth topic and bad at the third and fifth topic.

Output a single integer: the number of different good teams that can be created.

2 3
1 4

1

5 4
1 6 13 3 11

6

3 3
1 3 7

0