题目描述

你帮助 George 和 Alex 搬进宿舍后，他们又去和他们的朋友 Fedor 一起玩一款新的电脑游戏《士兵召唤 3》。

游戏共有 $(m+1)$ 名玩家和 $n$ 种士兵。《士兵召唤 3》中的玩家从 $1$ 到 $m+1$ 进行编号。士兵的编号范围为 $0 \sim (n−1)$。每个玩家都有一支军队。其中第 $i$ 个玩家的军队可以用非负整数 $x_i$ 来表示。

如果 $x_i$ 的二进制的第 $j$ 位等于 $1$，则第 $i$ 个玩家有编号为 $j$ 的士兵。

Fedor 是第 $(m+1)$ 个玩家。他假设如果两个玩家的军队最多有 $k$ 种类型的士兵不同(换句话说，对应数字的二进制表示最多有 $k$ 位数字不同)， 则两名玩家可以成为朋友。请你帮助费多尔并计算出有多少玩家可以和他成为朋友。

输入格式

第一行三个整数 $n,m,k$，$1\le k\le n\le 20$，$1\le m\le 1000$。

接下来 $(m+1)$ 行，每行一个整数 $x_i$，$1\le x_i\le 2^n-1$。

输出格式

输出一个整数表示答案。

7 3 1
8
5
111
17

0

3 3 3
1
2
3
4

3