Optimal Card Collection in a Two‐Player Card Game

Potter and Coco are playing a card game with an unusual deck‐building mechanism. There are \(m\) kinds of cards, and a card of type \(x\) has value \(x\). Initially no cards are unlocked. Potter performs \(n\) draws to build the deck. In the \(i\)th draw, \(a_i\) new card types become unlocked – that is, if before the draw the types \(1\) through \(s\) were unlocked, then after the draw types \(1\) through \(s+a_i\) are unlocked. It is guaranteed that \(\sum_{i=1}^{n} a_i = m\).

Then, in the \(i\)th draw, Potter chooses uniformly at random one of the unlocked card types and takes out two copies (of that type) and appends them (in order) to the right end of the deck. Thus, after \(n\) draws the deck is a row of \(2n\) cards. Note that the deck has a very special structure: for each draw \(i\) a pair of identical cards, both with value \(b_i\) (where \(b_i\) is chosen uniformly from \(\{1,2,\dots, s_i\}\) with \(s_i=\sum_{j=1}^{i}a_j\)), appears consecutively. Coco learns the value of every card in the deck (its order remains as generated).

The game is then played as follows. Coco and Potter pick cards alternately until no cards remain; Coco goes first. However, Potter always removes the leftmost card from the current deck, while Coco is free to choose any card in the deck. At each turn Coco wants to maximize the total value of the cards she collects at the end of the game. Let \(f(S)\) denote the maximum total value she may secure (when playing optimally) when the current deck is \(S\). In each round, Coco makes a move, obtaining a card of her choice, then Potter removes the leftmost card from the resulting deck. (Note that because the deck’s order is never rearranged, the removals always occur from the same relative positions.)

Since the deck is created randomly, the final optimal score for Coco is a random variable. Denote by \(C=\frac{A}{B}\) (with \(A\) and \(B\) coprime) the expected total value Coco obtains when playing optimally (the expectation is taken over all equally‐likely deck outcomes). You are to output the unique integer \(x\) between \(0\) and \(10^9+6\) such that

[ B, x \equiv A \pmod{10^9+7}. ]

Input format: The first line contains an integer \(n\). The second line contains \(n\) space–separated integers \(a_1,a_2,\dots,a_n\) (with \(\sum_{i=1}^n a_i = m\)).

Output format: Output a single integer representing the expected optimal total value modulo \(10^9+7\) (as explained above).

Note on formulas: All formulas must be rendered in LaTeX. For example, the expected value is given by \(E=\frac{A}{B}\) and the modular inverse is defined by \(B\, x\equiv A \pmod{10^9+7}\).

inputFormat

The first line contains an integer \(n\). The second line contains \(n\) space-separated integers \(a_1,a_2,\dots,a_n\). These determine that in the \(i\)th deck–building step the unlocked card types become \(\{1,2,\dots, s_i\}\), where \(s_i=\sum_{j=1}^{i}a_j\).

outputFormat

Output a single integer: the expected optimal value that Coco can get, modulo \(10^9+7\). Formally, if the expected value is \(E=\frac{A}{B}\) in lowest terms, output the unique \(x\) with \(0\le x<10^9+7\) such that \(B\, x\equiv A\pmod{10^9+7}\).

sample

1
3

2