Description

Let x be an integer chosen uniformly at random from [0, n). We need to find an integer y in [0, n) such that x ⊕ y is maximized. Here ⊕ denotes bitwise XOR.

The problem is that x may have been encrypted. Intelligence indicates that the probability that it was not encrypted is p. We adopt the following strategy: if x is not encrypted, we choose a y that maximizes x ⊕ y; otherwise, we choose y uniformly at random from [0, n).

Compute the expected value of x ⊕ y.

Input Format

The input consists of a single line containing a positive integer n and a real number p, as described above. The value p is given with up to six digits after the decimal point.

Output Format

Output a single line containing the expected value of x ⊕ y. Your answer will be accepted if its relative error does not exceed $10^{-5}$. It is recommended to keep at least six decimal places.

3 0.5

2.000000

123456 0.5

98063.674346

Hint

Consider Sample 1. If x is not encrypted, the possible values of x and the corresponding y are as follows:

The expected value in this case is 8/3.

If x is encrypted, the possible values of x and y are as follows:

The expected value in this case is 12/9 = 4/3.

Therefore, the overall expected value is 2.

The data scale for all test points is as follows:

Constraints: For all testdata, $1 \le n \le 10^{18}$.

Translated by ChatGPT 5