Después de haber ayudado a George y Alex a mudarse al dormitorio, fueron a ayudar a su amigo Fedor a jugar un nuevo juego de computadora, Call of Soldiers 3.

El juego tiene ($m+1$) jugadores y $n$ tipos de soldados en total. Los jugadores de Call of Soldiers 3 están numerados del $1$ al ($m$ + $1$). Los tipos de soldados están numerados del $0$ al $n$ – $1$. Cada jugador tiene un ejército. El ejército del i-ésimo jugador puede describirse mediante un número entero no negativo $x_i$. Considere la representación binaria de $x_i$: si el j-ésimo bit del número $x_i$ es igual a uno, entonces el ejército del i-ésimo jugador tiene soldados del j-ésimo tipo.

Fedor es el (m + 1)-ésimo jugador del juego. Suponga que dos jugadores pueden hacerse amigos si sus ejércitos difieren en $k$ tipos de soldados como máximo (en otras palabras, las representaciones binarias de los números correspondientes difieren en $k$ bits como máximo). Ayuda a Fedor y cuenta cuántos jugadores pueden convertirse en sus amigos.

Entrada

La primera línea contiene tres números enteros $n$, $m$, $k$ ($1\le k\le n\le 20$; $1\le m\le 1000$).

La i-ésima de las siguientes ($m$ + $1$) líneas contiene un solo número entero $x_i$ ($1\le x_i\le 2^n$ – $1$), que describe el ejército del i-ésimo jugador. Les recordamos que Fedor es el (m + 1)-ésimo jugador.

Salida

Imprime un solo entero: el número de amigos potenciales de Fedor.

Ejemplo de Entrada 1

7 3 1
8
5
111
17

Ejemplo de Salida 1

0

Ejemplo de Entrada 2

3 3 3
1
2
3
4

Ejemplo de Salida 2

3