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 \leq k \leq n \leq 20~; ~1 \leq m \leq 1000~).

La i-ésima de las siguientes (~m~ + ~1~) líneas contiene un solo número entero ~x_i~ (~1 \leq x_i \leq 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