Vasya 具有由 n 个整数组成的序列。 Vasya 认为整数对 x 和 y k 是有趣的,如果它们的二进制表示在 k 位上彼此完全不同。例如,如果 k = 2,则整数对 x = 5 和 y = 3 是 k 有趣的,因为它们的二进制表示形式 x=101 和 y=011 恰好有两位不同。
Vasya 想知道他的序列中有多少对索引 (i, j),使得 i < j 并且整数对 ai 和 aj 是 k-感兴趣的。你的任务是帮助 Vasya 并确定这个数字。
输入
第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 0 ≤ k ≤ 14) — Vasya 序列中整数的数量以及 k 感兴趣对中整数应该不同的位数。
第二行包含 Vasya 拥有的序列 a1, a2, ..., an (0 ≤ ai ≤ 104)。
输出
打印 (i, j) 对的数量,使得 i < j 并且整数对 ai 和 aj 是 k 感兴趣的。
示例
输入 #1
4 1 0 3 2 1
输出 #1
4
输入 #2
6 0 200 100 100 100 200 200
输出 #2
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).