D. k-Интересные пары чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть последовательность, состоящая из n целых чисел. Вася считает пару чисел x и y k-интересной, если их двоичное представление отличается друг от друга ровно в k битах. Например, если k = 2, то пара чисел x = 5 и y = 3 является k-интересной, так как двоичные представления x=101 и y=011 отличаются ровно в двух битах.

Васе стало интересно, сколько в его последовательности существует пар индексов (i, j) таких, что i < j и пара чисел ai и aj является k-интересной. Перед вами стоит задача помочь Васе и определить это количество.

Входные данные

В первой строке следует два целых числа n и k (2 ≤ n ≤ 105, 0 ≤ k ≤ 14) — количество чисел в последовательности Васи и количество битов, в которых должны отличаться числа в k-интересной паре.

Во второй строке следует последовательность a1, a2, ..., an (0 ≤ ai ≤ 104), которая есть у Васи.

Выходные данные

Выведите количество пар (i, j) таких, что i < j и пара чисел ai и aj является k-интересной.

Примеры
Входные данные
4 1
0 3 2 1
Выходные данные
4
Входные данные
6 0
200 100 100 100 200 200
Выходные данные
6
Примечание

В первом примере существует 4 k-интересные пары:

  • (1, 3),
  • (1, 4),
  • (2, 3),
  • (2, 4).

Во втором примере k = 0. Следовательно, числа в любой k-интересной паре должны быть равны между собой. Таким образом, для второго примера существует 6 k-интересных пар:

  • (1, 5),
  • (1, 6),
  • (2, 3),
  • (2, 4),
  • (3, 4),
  • (5, 6).