题目描述

有一个在 [0,n) 内等概率随机选择的整数，记其为 x。我们需要在 [0,n)内找到某一个整数 y，使得 x ⊕ y 达到最大值。这里 ⊕ 代表异或。

问题在于，有可能对 x 进行了加密。情报显示，没有被加密的概率为 p。我们决定采取这样的策略：如果 x 没有被加密，那么我们选出使得 x ⊕ y 最大的 y；否则，我们在 [0,n) 内等概率随机选择一个整数作为 y。

请求出 x ⊕ y 的期望值。

输入格式

输入文件仅包含一行，其中有一个正整数 n 和一个实数 p，含义如问题描述中所述。 p 至多精确到小数点后六位。

输出格式

输出一行，代表 x ⊕ y 的期望值。只有当你的输出与标准输出的相对误差不超过 $10^{-5}$ 时，你的输出才会被判为正确。建议保留至少六位小数。

3 0.5

2.000000

123456 0.5

98063.674346

提示

考虑样例一。如果 x 没有被加密，那么可能的 x 与对应的 y 的取值如下：

此时的期望值为 8/3。

如果大新闻被加密了，那么可能的 x 和 y 的取值如下：

此时的期望值为 12/9 = 4/3。

所以总的期望值为 2。

所有测试点的数据规模如下：

对于全部测试数据，$1 \le n \le 10^{18}$。