在你帮助乔治和亚历克斯搬进宿舍后,他们去帮助他们的朋友费多尔玩一个新的电脑游戏《士兵召唤3》。
游戏共有(m+1)名玩家和n种士兵。 《Call of Soldiers 3》玩家的编号从 1 到 (m + 1)。士兵的类型从0到n-1编号。每个玩家都有一支军队。第 i 个玩家的军队可以用非负整数 xi 来描述。考虑 xi 的二进制表示:如果数字 xi 的第 j 位等于 1,则第 i 个玩家的军队拥有第 j 种类型的士兵。
Fedor 是游戏中的第 (m + 1) 位玩家。他假设,如果两个玩家的军队最多有 k 种类型的士兵不同(换句话说,相应数字的二进制表示最多有 k 位不同),那么两个玩家就可以成为朋友。帮助费多并计算有多少玩家可以成为他的朋友。
输入
第一行包含三个整数 n、m、k (1 ≤ k ≤ n ≤ 20;1 ≤ m ≤ 1000)。
接下来的 (m + 1) 行的第 i 行包含一个整数 xi (1 ≤ xi ≤ 2n - 1),它描述了第 i 个玩家的军队。我们提醒您,Fedor 是第 (m + 1) 位玩家。
输出
打印一个整数——Fedor 潜在朋友的数量。
示例
输入 #1
7 3 1 8 5 111 17
输出 #1
0
输入 #2
3 3 3 1 2 3 4
输出 #2
3