题目描述

已知一个长度为 $n$ 的正整数序列 $A$（下标从 $1$ 开始）， 令 $S = \{ x \mid 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)$，对于一切 $t$ 属于 $T$ 现在 albus 把 $2^S$ 中每个集合的 $f$ 值计算出来， 从小到大排成一行，记为序列 $B$（下标从 $1$ 开始）。给定一个数，那么这个数在序列 $B$ 中第 $1$ 次出现时的下标是多少呢？

输入格式

第一行一个数 $n$, 为序列 $A$ 的长度。接下来一行 $n$ 个数， 为序列 $A$， 用空格隔开。最后一个数 $Q$， 为给定的数。

输出格式

共一行，一个整数，为 $Q$ 在序列 $B$ 中第一次出现时的下标模 $10086$ 的值。

3
1 2 3
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 xor 2 = 3$

$f(\{1, 3\}) = 1 xor 3 = 2$

$f(\{2, 3\}) = 2 xor 3 = 1$

$f(\{1, 2, 3\}) = 0$

所以 $B = [0, 0, 1, 1, 2, 2, 3, 3]$。

数据规模与约定

$1 \le N \le 10,0000$，其他所有输入均不超过$10^9$。