Description

Cool has now figured out the layout of the women’s dormitory. The dormitory consists of many buildings, which can be abstracted as a $20\times 20$ grid.

The places where Cool’s maids are located can be represented by real-valued coordinates. A maid $(x, y)$ is in building $(i, j)$ if and only if $i \le x < i + 1$, $j \le y < j + 1$, $i, j \in \Z$. The distance between two maids is defined if and only if both the row and column indices of one maid’s building are strictly less than those of the other maid’s building; in that case, their distance is the Manhattan distance between their own coordinates.

Now Cool wants to compile a big statistic: compute the sum of all distances among $n$ maids.

Input Format

To avoid spending too much time on reading due to large input files that cannot be uploaded, this problem uses a data generation scheme.

The input contains two lines:

• The first line contains an integer $n$.
• The second line contains $6$ integers $\mathrm{rxa}, \mathrm{rxc}, \mathrm{rya}, \mathrm{ryc}, \mathrm{rza}, \mathrm{rzc}$.

All real numbers are generated as follows:

1. Initialize $x = y = z = 0$.
2. Repeat the following process:
   • $x = (y \times \mathrm{rxa} + \mathrm{rxc}) \bmod \mathrm{rp}$;
   • $y = (z \times \mathrm{rya} + \mathrm{ryc}) \bmod \mathrm{rp}$;
   • $z = (x \times \mathrm{rza} + \mathrm{rzc}) \bmod \mathrm{rp}$.

Each time, the real number obtained is $(x \bmod 20) + (y \bmod 10) \div 10 + (z \bmod 10) \div 100$. $\mathrm{rp} = 2333333$.

The $i$-th maid uses the $(2i - 1)$-th generated real number as the $x$-coordinate, and the $2i$-th generated real number as the $y$-coordinate.

Output Format

Output a single real number on one line, representing the average of all distances among the $n$ maids, with $5$ decimal places.

6
3 5 7 11 13 17

17.52167

Hint

Constraints

For all testdata, it is guaranteed that $1 \le n \le 5 \times 10^6$.

Translated by ChatGPT 5