Description

gx and lc went to take the NOIP preliminary round. There is a type of problem called single-choice questions, meaning only one option is the correct answer.

There are $n$ single-choice questions on the paper. The $i$-th question has $a_i$ options, numbered $1, 2, 3, \ldots, a_i$. Each option is equally likely to be the correct answer.

lc’s strategy is to randomly write down some number from $1 \sim a_i$ as the answer for each question. In little time, he can expect to get $\sum_{i=1}^n \frac{1}{a_i}$ questions correct. gx carefully solved all $n$ questions, but when he finished, time was running out. He hurriedly copied his answers onto the answer sheet, but accidentally shifted them: the answer to the $i$-th question was written in the position of the $(i+1)$-th question on the answer sheet. Specifically, the answer to the $n$-th question was written in the position of the $1$-st question.

Now that gx has left the exam room, he cannot change his answers, but he still wants to know the expected number of questions he got correct, so he can tell whether he will be looked down upon by lc.

We assume gx did not solve any question incorrectly; only the positions of his answers were misaligned.

Input Format

$n$ is large. To avoid slow input, the input file contains only $5$ integers $n, A, B, C, a_1$, and the submitted program generates the sequence $a$. Below are the Pascal/C/C++ input statements and the sequence-generation statements (input is read from standard input by default):

// for pascal
readln(n,A,B,C,q[1]);
for i:=2 to n do
q[i] := (int64(q[i-1]) * A + B) mod 100000001;
for i:=1 to n do
q[i] := q[i] mod C + 1;


// for C/C++
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
	a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
	a[i] = a[i] % C + 1;

Contestants can obtain $n$ and the sequence $a$ using the code above (the elements of $a$ are $32$-bit integers). The meanings of $n$ and $a$ are as described in the problem statement.

Output Format

Output a real number representing the expected number of questions gx gets correct, rounded to three decimal places.

3 2 0 4 1

1.167

Hint

[Sample Explanation]

$a = \{2,3,1\}$.

There are $6$ cases, each occurring with probability $\frac{1}{6}$. The expected number of correct answers for gx is $\frac{3+1+1+1+1+0}6 = \frac76$. (In comparison, lc’s random strategy yields an expectation of $\frac{11}6$.)

For $30\%$ of the testdata, $n \le 10$, $C \le 10$.

For $80\%$ of the testdata, $n \le 10^4$, $C \le 10$.

For $90\%$ of the testdata, $n \le 5 \times 10^5$, $C \le 10^8$.

For $100\%$ of the testdata, $2 \le n \le 10^7$, $0 \le A, B, C \le 10^8$, $1 \le a_i \le 10^8$.

Translated by ChatGPT 5