A9615 | Fedor and New Game

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.