Wandering

Rikka is a talented student.

She likes to wander in the corridor while solving ICPC problems. Specifically, she takes a random walk of $n$ steps. In the $i$-th random step, she chooses one of the vectors $(x, y)$ such that $x, y \in \mathbb{R}$ and $x^2 + y^2 \le R_i^2$ with equal probability. Then she walks along that vector. In other words, if she stood at $(A, B)$ before the random step, she stands at $(A + x, B + y)$ afterwards. Before wandering, she stands at the door $(0, 0)$.

After wandering, she became curious about the expected value of the square of the Euclidean distance to the point $(0, 0)$. In other words, if she stands at $(x, y)$ after all $n$ random steps, she wants to know the expected value of $x^2 + y^2$.

The first line contains an integer $n$, the number of random steps.

The second line contains $n$ positive integers $R_i$, the parameter of the $i$-th random step.

It is guaranteed that $1 \le n \le 50\,000$ and $1 \le R_i \le 1000$.

You must output $d$, the expected value of $x^2 + y^2$. Letting the correct answer be $d^*$, you must ensure that $\frac{|d - d^*|}{\max\{d^*, 1\}} \leq 10^{-6}$.