Problem Description

Given a positive integer sequence $A$ of length $n$ (indices start from $1$), let $S = \{ x | 1 \le x \le n \}$. The power set $2^S$ is defined as the set consisting of all subsets of $S$. Define a mapping $f : 2^S \to Z$, where $f(\emptyset) = 0$, and for a non-empty set $T$, $f(T) = \mathrm{XOR}\{A_t\}, (t \in T)$.

Now Albus computes the value $f$ for every set in $2^S$, sorts these values in non-decreasing order into a sequence, and denotes it as sequence $B$ (indices start from $1$).

Given a number, what is the index of its first occurrence in sequence $B$?

Input Format

The first line contains an integer $n$, the length of sequence $A$. The next line contains $n$ integers representing $A$, separated by spaces. The last number is $Q$, the given number.

Output Format

Output one line with one integer: the value of the index of the first occurrence of $Q$ in sequence $B$ modulo $10086$.

3
1 2 3
1

3

Hint

[Sample Explanation]

$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$
Therefore,
$B = [0,0,1,1,2,2,3,3]$

[Constraints]

$1 \leq N \leq 10,0000$
All other inputs do not exceed $10^9$.

Translated by ChatGPT 5