题目描述

在虚拟的游戏世界“士兵突击 $3$”中， $(m+1)$ 名玩家组建了自己的军队。这个游戏中共有 $n$ 种不同的士兵，兵种编号为 $0$ 至 $n - 1$，每种士兵都拥有独特的能力和特点。每位玩家的军队由这些士兵组成，而军队的构成可以用一个非负整数 $x_i$ 来表示。

具体来说，如果 $x_i$ 的二进制表示中第 $j$ 位是 $1$，那么意味着这位玩家的军队中拥有第 $j$ 种士兵。比如，如果 $x_i$ 是 $5$（二进制表示为 $101$），那么这位玩家的军队就拥有第 $0$ 种和第 $2$ 种士兵。

小可作为游戏的第 $(m+1)$ 名玩家，希望找到那些能与她并肩作战的战友。她认为，只要两位玩家的军队中最多只有 $k$ 种不同的士兵，那么他们就可以成为朋友。换句话说，就是他们军队数字的二进制表示最多只有 $k$ 位不同。

现在，请你帮助小可计算一下，在这个游戏世界中，有多少玩家可以成为她的朋友。

输入格式

• 第一行包含三个整数 $n、m、k$，表示士兵种类数、战友数量（不包括小可）和最多允许的不同士兵种类数。
• 接下来的 $m + 1$ 行，每行包含一个整数 $x_i$，表示第 $i$ 位玩家的军队构成。

输出格式

输出一个整数，表示可以成为小可盟友的玩家数量。

样例

7 3 1
8
5
111
17

0

3 3 3
1
2
3
4

3

提示

样例1解释

• 7：表示游戏中总共有 $7$ 种不同的士兵（编号从 $0$ 到 $6$ ）。
• 3：表示有 $3$ 位玩家（不包括小可）的军队构成被给出。
• 1：表示小可认为只要两位玩家的军队在士兵种类上最多只有 $1$ 种不同，那么他们就可以成为朋友。

接下来是四行数字，分别表示四位玩家（包括小可）的军队构成：

• 第一个数字8（二进制0001000）表示第一位玩家的军队中只有第 $3$ 种士兵。
• 第二个数字5（二进制0000101）表示第二位玩家的军队中有第 $0$ 种和第 $2$ 种士兵。
• 第三个数字111（二进制1101111），表示第三位玩家的军队中有第$0、1、2、3、5、6$种士兵。
• 第四个数字17（二进制0010001）表示小可（作为第4位玩家）的军队中有第 $0$ 种和第 $4$ 种士兵。

由于没有玩家的军队构成与小可的军队构成在士兵种类上最多只有 $1$ 种不同，所以输出为0。

数据范围

• $1 \le k \le n \le 20$;
• $1 \le m \le 1000$;
• $1 \le x_i \le 2^n - 1$。