2681. k次按位异或

【题目描述】

给出 $n$ 个整数 $a_i$，从中选出 $k$ 个（可以重复），接下来有 $Q$ 个询问，每次给出一个整数 $x$，表示有多少种方案，使得选出的 $k$ 个按位异或等于 $x$。两种方案不同当且仅存在一个 $j$，使得选择的第 $j$ 个数的下标不同。方案数对 $10007$ 取模。

【输入格式】

第一行两个整数 $n$ 和 $k$;

第二行 $n$ 个正整数，表示 $a_i$;

接下来一个整数 $Q$;

接下来一行 $Q$ 个整数 $x$，整数均非负。

【输出格式】

$Q$ 行，每行一个整数，表示该次询问的答案。

【样例输入】

4 3
1 2 3 1
7
0 1 2 3 4 5 6

【样例输出】

12
20
16
16
0
0
0

【数据规模】

$n,q \leq 1e5，a_i,x \leq (1<<17)，k \leq 1e9$。

【来源】

Mike位运算题组T6