Diane wants to host her own dating gameshow... on Zoom! Her brilliant idea is to continuously eliminate contestants (uniquely identified by an integer between $1$ and $N$) at random until only two remain, and then have the lucky pair go on a private getaway. Diane would like to use the features of Zoom to her advantage to handle her elimination process (and increase her showmanship).
At the top of her meeting, there is a bar of video screens showing all original contestants (assume that Diane's video screen is not included). We can think of this as a permutation array, where the $i$-th element represents the video of some unique contestant. Every elimination will be conducted by Diane flipping a fair coin. A flip of heads will result in the video screen furthest to the left being kicked out of the meeting, while a flip of tails will result in the video screen furthest to the right being kicked out of the meeting. This elimination process will end when exactly two (future) lovers remain on the bar of video screens.
The "compatibility index" of two contestants can be computed as the bitwise XOR of their assigned ID. Can you help Diane calculate the expected value of the compatibility index of the winning couple?
There are two lines in each test case.
The first line contains a single integer $N$ ($2 <= N <= 2000$) representing the number of original contestants in the Zoom room.
The second line contains $N$ unique space separated integers $c_i$ ($1 <= c_i <= N$) representing the original ordering of contestants in the bar of video screens.
Output a single integer representing the calculated expected value of the compatibility index times $2^(N -2)$ modulo $10^9 + 7$.
In the first sample, we do not eliminate any contestants and our expected value is simply $2 plus.circle 1 = 3$.
In the second sample, there is a $frac(1, 4)$ chance we end up with $(3, 1)$, a $frac(1, 2)$ chance we end up with $(1, 2)$, and a $frac(1, 4)$ chance we end up with $(2, 4)$. Our expected value is thus $frac(1, 4) dot.op 2 + frac(1, 2) dot.op 3 + frac(1, 4) dot.op 6 = frac(7, 2)$.
## Input
There are two lines in each test case.The first line contains a single integer $N$ ($2 <= N <= 2000$) representing the number of original contestants in the Zoom room.The second line contains $N$ unique space separated integers $c_i$ ($1 <= c_i <= N$) representing the original ordering of contestants in the bar of video screens.
## Output
Output a single integer representing the calculated expected value of the compatibility index times $2^(N -2)$ modulo $10^9 + 7$.
[samples]
## Note
In the first sample, we do not eliminate any contestants and our expected value is simply $2 plus.circle 1 = 3$.In the second sample, there is a $frac(1, 4)$ chance we end up with $(3, 1)$, a $frac(1, 2)$ chance we end up with $(1, 2)$, and a $frac(1, 4)$ chance we end up with $(2, 4)$. Our expected value is thus $frac(1, 4) dot.op 2 + frac(1, 2) dot.op 3 + frac(1, 4) dot.op 6 = frac(7, 2)$.
**Definitions**
Let $ N \in \mathbb{Z} $ with $ 2 \leq N \leq 2000 $ be the number of contestants.
Let $ C = (c_1, c_2, \dots, c_N) $ be a permutation of $ \{1, 2, \dots, N\} $, representing the initial ordering of contestants on screen.
Let $ S \subseteq \{1, 2, \dots, N\} $ be the set of two remaining contestants after $ N-2 $ random eliminations, where at each step the leftmost or rightmost contestant is removed with equal probability $ \frac{1}{2} $.
Let $ \oplus $ denote bitwise XOR. The compatibility index of a pair $ (a, b) $ is $ a \oplus b $.
**Constraints**
- Each elimination removes either the first or last element of the current contiguous subarray of $ C $.
- The process ends when exactly two contiguous elements remain.
- All $ 2^{N-2} $ possible elimination sequences are equally likely.
**Objective**
Compute:
$$
\left( \sum_{\text{all valid remaining pairs } (c_i, c_j)} \left( \text{number of paths to } (c_i, c_j) \right) \cdot (c_i \oplus c_j) \right) \mod (10^9 + 7)
$$
where the remaining pair $ (c_i, c_j) $ must be contiguous in the original array $ C $, i.e., $ j = i + 1 $, and the number of paths to leave $ (c_i, c_{i+1}) $ is $ 2^{N-2} $ times the probability of that pair surviving.
Equivalently, since each valid pair $ (c_i, c_{i+1}) $ for $ i \in \{1, \dots, N-1\} $ can be the final pair, and the number of elimination sequences resulting in $ (c_i, c_{i+1}) $ is $ \binom{N-2}{i-1} $, the expected value multiplied by $ 2^{N-2} $ is:
$$
\sum_{i=1}^{N-1} \binom{N-2}{i-1} \cdot (c_i \oplus c_{i+1})
$$