albus就是要第一个出场
题目描述
已知一个长度为 $n$ 的正整数序列 $A$(下标从 $1$ 开始),令 $S = \{ x | 1 \le x \le n \}$,$S$ 的幂集 $2^S$ 定义为 $S$ 所有子集构成的集合。定义映射 $f : 2^S \to Z,f(\emptyset) = 0,f(T) = \mathrm{XOR}\{A_t\}, (t \in T)$。
现在 albus 把 $2^S$ 中每个集合的 $f$ 值计算出来,从小到大排成一行,记为序列 $B$(下标从 $1$ 开始)。
给定一个数,那么这个数在序列 $B$ 中第 $1$ 次出现时的下标是多少呢?
输入输出格式
输入格式
第一行一个数 $n$, 为序列 $A$ 的长度。接下来一行 $n$ 个数,为序列 $A$,用空格隔开。最后一个数 $Q$,为给定的数.
输出格式
共一行,一个整数,为 $Q$ 在序列 $B$ 中第一次出现时的下标模 $10086$ 的值.
输入输出样例
输入样例 #1
3
1 2 3
1
输出样例 #1
3
说明
【样例解释】
$N = 3,A = [1,2,3]$
$S = \{1,2,3\}$
$2^S = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$
$f(\emptyset) = 0$
$f({1}) = 1$
$f({2}) = 2$
$f({3}) = 3$
$f({1, 2}) = 1 \operatorname{xor} 2 = 3$
$f({1, 3}) = 1 \operatorname{xor} 3 = 2$
$f({2, 3}) = 2 \operatorname{xor} 3 = 1$
$f({1, 2, 3}) = 0$
所以
$B = [0,0,1,1,2,2,3,3]$
【数据范围】
$1 \leq N \leq 10,0000$
其他所有输入均不超过 $10^9$