Fedor and New Game

题意翻译

你帮助 George 和 Alex 搬进宿舍后，他们又去和他们的朋友 Fedor 一起玩一款新的电脑游戏《士兵召唤3》。 游戏共有 $(m+1)$ 名玩家和 $n$ 种士兵。《士兵召唤3》中的玩家从 $1$ 到 $m+1$ 进行编号。士兵的编号范围为 $0$ ~ $(n−1)$ 。每个玩家都有一支军队。其中第 $i$ 个玩家的军队可以用非负整数 $x_{i}$ 来表示。 如果 $x_{i}$ 的二进制的第 $j$ 位等于 $1$ , 则第 $i$ 个玩家有编号为 $j$ 的士兵。 Fedor 是第 $(m+1)$ 个玩家。他假设如果两个玩家的军队最多有 $k$ 种类型的士兵不同(换句话说，对应数字的二进制表示最多有 $k$ 位数字不同)， 则两名玩家可以成为朋友。请你帮助费多尔并计算出有多少玩家可以和他成为朋友。

题目描述

After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3». The game has $ (m+1) $ players and $ n $ types of soldiers in total. Players «Call of Soldiers 3» are numbered form $ 1 $ to $ (m+1) $ . Types of soldiers are numbered from $ 0 $ to $ n-1 $ . Each player has an army. Army of the $ i $ -th player can be described by non-negative integer $ x_{i} $ . Consider binary representation of $ x_{i} $ : if the $ j $ -th bit of number $ x_{i} $ equal to one, then the army of the $ i $ -th player has soldiers of the $ j $ -th type. Fedor is the $ (m+1) $ -th player of the game. He assume that two players can become friends if their armies differ in at most $ k $ types of soldiers (in other words, binary representations of the corresponding numbers differ in at most $ k $ bits). Help Fedor and count how many players can become his friends.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , $ k $ $ (1<=k<=n<=20; 1<=m<=1000) $ . The $ i $ -th of the next $ (m+1) $ lines contains a single integer $ x_{i} $ $ (1<=x_{i}<=2^{n}-1) $ , that describes the $ i $ -th player's army. We remind you that Fedor is the $ (m+1) $ -th player.

输出格式

Print a single integer — the number of Fedor's potential friends.

输入输出样例

输入样例 #1

7 3 1
8
5
111
17

输出样例 #1

0

输入样例 #2

3 3 3
1
2
3
4

输出样例 #2

3