Counting Valid Team Arrangements

In the headquarters of ENLIGHTENED, there are N agents with distinct ability values. The ENLIGHTENED行动指挥 wants to form two teams A and B to participate in the XM大战. However, the two teams must satisfy the following conditions:

1. The maximum ability in team A is strictly less than the minimum ability in team B, i.e. if A and B are the sets of agents chosen for the teams, then \[ \max(A) < \min(B). \]
2. Both teams must have at least one agent.

Note that not all agents have to participate in the battle. Given these conditions, determine the number of ways to choose two groups (team A and team B) from the N agents such that the above condition is satisfied. Since the answer can be very large, output it modulo \(10^9+7\).

Hint: Sort the agents by their abilities. Any valid arrangement can be represented by choosing an index \(k\) (with \(1 \le k < N\)) such that team A consists of any non-empty subset of the first \(k\) agents and team B consists of any non-empty subset of the remaining \(N-k\) agents. The answer is then given by

[ \sum_{k=1}^{N-1} \Bigl((2^k-1)\cdot(2^{N-k}-1)\Bigr)\mod (10^9+7). ]

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 10⁵), representing the number of agents.

The second line contains N distinct integers, where each integer represents the ability of an agent.

outputFormat

Output a single integer — the number of valid arrangements modulo \(10^9+7\).

sample

2
1 2

1