Background

Problem Description

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).

Input Format

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

Output Format

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

2
114514 1919810

114514

3
1 1 2

4

Hint

Explanation for Sample $1$

Choose $x=2$, and perform $114514$ operations, each time taking $y=1$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $2\le n\le 10^6$ and $0\le a_i<1004535809$.

Translated by ChatGPT 5