Description

Apple really likes eating chocolate, but it is a picky pig, and some kinds of chocolate cannot satisfy its taste. If the owner gives it chocolate that it does not like, it will be very unhappy. The owner does not know what kind of chocolate Apple likes, but she knows that the cocoa content is an important factor affecting a chocolate’s taste, so she decides to judge which chocolates to give Apple based on their cocoa content.

Assume that the cocoa content of a chocolate has $1\sim N$ different measured levels. She considers chocolates whose cocoa content lies in the range $[a,b]$ to be tasty. However, she does not know what this range is, and you need to help determine a range so that she can let Apple eat as many chocolates it likes as possible.

Let $pos_i$ be the number of chocolates with cocoa butter content $i$ that Apple thinks are tasty, and let $neg_i$ be the number of chocolates with cocoa butter content $i$ that Apple thinks are not tasty. These two sequences are generated as follows:

$$\begin{cases}pos_i=a_{2i-1}\\neg_i=a_{2i}\end{cases}$$

where $a_i=(p_1a_{i-1}+p_2)\bmod M(i>1)$.

Let $TP$ be the number of chocolates that Apple thinks are tasty and the owner also judges as tasty, $TN$ be the number of chocolates that Apple thinks are not tasty and the owner also judges as not tasty, $FP$ be the number of chocolates that Apple thinks are not tasty but the owner judges as tasty, and $FN$ be the number of chocolates that Apple thinks are tasty but the owner judges as not tasty.

Let $r$ be the ratio of chocolates correctly judged as tasty among all truly tasty chocolates, and let $p$ be the ratio of chocolates correctly judged as tasty among all chocolates judged as tasty. Then

$$\begin{cases}r=\frac{TP}{TP+FN}\\p=\frac{TP}{TP+FP}\end{cases}$$

Please help Apple find a range that maximizes $f=\frac{2pr}{p+r}$.

Input Format

The input consists of multiple lines. Each line is one dataset: $N,a_1,p_1,p_2,M$, separated by spaces.

The input ends with a single $0$. The number of datasets does not exceed $1000$.

Output Format

For each dataset, output one line: the maximum value of $f$ (rounded to $6$ decimal places).

4 4 4 1 5
12 9 6 6 11
0

0.800000
0.683938

Hint

Constraints

For $100\%$ of the testdata, $1\leq N\leq 10^6,a_1,p_1,p_2<M\leq 20$. It is guaranteed that there is at least one chocolate that Apple thinks is tasty.

Translated by ChatGPT 5