P8850 [JRKSJ R5] Jalapeno and Garlic


There is a cycle with $n$ vertices. Each vertex has a weight $a$, and the vertices are numbered from $1$ to $n$. Vertex $1$ is adjacent to vertex $n$. You want there to be exactly one $x\in[1,n]$ such that $a_x\ne 0$. To achieve this, you need to perform operations according to the following process: 1. Choose an $x$, meaning that in the end you want $a_x\ne 0$. **After that, you cannot change your choice of $x$.** 2. Perform some number of modification operations. In each operation, you may choose a $y\in[1,n]$ and set $a_y\gets a_y-1$. At the same time, among the two vertices adjacent to $y$, **choose one uniformly at random**, and its weight will be increased by $1$. You want the expected number of modification operations to be as small as possible. Therefore, compute the expected number of operations under the optimal strategy (operation 1 is not counted).

The first line contains an integer $n$.\ The second line contains $n$ integers representing $a_{1\dots n}$.

Output an integer representing the answer. Print the answer modulo $1004535809$.

### Explanation for Sample $1$ Choose $x=2$, and perform $114514$ operations, each time taking $y=1$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n\le$ | Score | | :----------: | :----------: |:----------: | | $1$ | $2$ | $5$ | | $2$ | $10^3$ | $20$ | | $3$ | $10^4$ | $20$ | | $4$ | $10^5$ | $20$ | | $5$ | $10^6$ | $35$ | For $100\%$ of the testdata, $2\le n\le 10^6$ and $0\le a_i