题目描述

在你帮 George 和 Alex 搬进宿舍之后，他们去帮他们的朋友 Fedor 玩一款新的电脑游戏《Call of Soldiers 3》。

游戏总共有 $m+1$ 个玩家，以及 $n$ 种士兵类型。玩家编号为 $1$ 到 $m+1$，士兵类型编号为 $0$ 到 $n-1$。每个玩家都有一支军队。第 $i$ 个玩家的军队可以用一个非负整数 $x_i$ 描述。考虑 $x_i$ 的二进制表示：如果第 $j$ 位是 $1$，则第 $i$ 个玩家的军队中拥有编号为 $j$ 的士兵。

Fedor 是第 $(m+1)$ 个玩家。他认为，如果两名玩家的军队至多有 $k$ 种类型的士兵不同（换句话说，两数的二进制表示有至多 $k$ 位不同），那么这两名玩家就可以成为朋友。请你帮助 Fedor 计算有多少玩家可以成为他的朋友。

输入格式

第一行包含三个整数 $n$、$m$、$k$，满足 $1 \leq k \leq n \leq 20,\ 1 \leq m \leq 1000$。

接下来的 $(m+1)$ 行，每行包含一个整数 $x_i\ (1 \leq x_i \leq 2^n - 1)$，表示第 $i$ 个玩家的军队。最后一行为 Fedor 的军队。

输出格式

输出一个整数，表示可以成为 Fedor 朋友的玩家人数。

说明/提示

由 ChatGPT 5 翻译

样例

7 3 1
8
5
111
17

0

3 3 3
1
2
3
4

3