407257: GYM102726 I Diane's Dating Game

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 \leq N \leq 2000$$$) representing the number of original contestants in the Zoom room.

The second line contains $$$N$$$ unique space separated integers $$$c_i$$$ ($$$1 \leq c_i \leq 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$$$.

2
2 1

3

4
3 1 2 4

14

In the first sample, we do not eliminate any contestants and our expected value is simply $$$2 \oplus 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} \cdot 2 + \frac{1}{2} \cdot 3 + \frac{1}{4} \cdot 6 = \frac{7}{2}$$$.