CF618G.Combining Slimes

Your friend recently gave you some slimes for your birthday. You have a very large amount of slimes with value 1 and 2, and you decide to invent a game using these slimes.

You initialize a row with n empty spaces. You also choose a number p to be used in the game. Then, you will perform the following steps while the last space is empty.

1. With probability , you will choose a slime with value 1, and with probability , you will choose a slime with value 2. You place the chosen slime on the last space of the board.
2. You will push the slime to the left as far as possible. If it encounters another slime, and they have the same value v, you will merge the slimes together to create a single slime with value v + 1. This continues on until the slime reaches the end of the board, or encounters a slime with a different value than itself.

You have played the game a few times, but have gotten bored of it. You are now wondering, what is the expected sum of all values of the slimes on the board after you finish the game.

你的朋友最近送了你一些史莱姆作为生日礼物。你拥有大量价值为 1 和 2 的史莱姆，于是决定用它们发明一个游戏。

你初始化一行包含 $n$ 个空格的棋盘。你还选定一个数字 $p$ 用于该游戏。然后，只要最后一格为空，你就重复执行以下步骤：

1. 以概率 选择一个价值为 1 的史莱姆，以概率 选择一个价值为 2 的史莱姆，并将所选史莱姆放置在棋盘最右侧的空格中。
2. 你将该史莱姆尽可能向左推动。若它遇到另一个史莱姆，且二者具有相同的价值 $v$，则将这两个史莱姆合并为一个价值为 $v+1$ 的新史莱姆。此过程持续进行，直到该史莱姆抵达棋盘最左端，或遇到一个与其价值不同的史莱姆为止。

你已玩过几次该游戏，但现已感到厌倦。你现在好奇的是：当游戏结束时，棋盘上所有史莱姆的价值之和的期望值是多少？

The first line of the input will contain two integers n, p (1 ≤ n ≤ 109, 1 ≤ p < 109).

输入的第一行包含两个整数 $n$ 和 $p$（$1 ≤ n ≤ 10^9$，$1 ≤ p < 10^9$）。

Print the expected sum of all slimes on the board after the game finishes. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely, let's assume that your answer is a and the answer of the jury is b. The checker program will consider your answer correct, if .

输出游戏结束后棋盘上所有史莱姆的期望总和。若你的答案绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

即，假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

In the first sample, we have a board with two squares, and there is a 0.5 probability of a 1 appearing and a 0.5 probability of a 2 appearing.

Our final board states can be 1 2 with probability 0.25, 2 1 with probability 0.375, 3 2 with probability 0.1875, 3 1 with probability 0.1875. The expected value is thus (1 + 2)·0.25 + (2 + 1)·0.375 + (3 + 2)·0.1875 + (3 + 1)·0.1875 = 3.5625.

在第一个样例中，我们有一个包含两个方格的棋盘，数字 1 出现的概率为 0.5，数字 2 出现的概率也为 0.5。

最终棋盘状态可能为：1 2（概率为 0.25）、2 1（概率为 0.375）、3 2（概率为 0.1875）、3 1（概率为 0.1875）。因此，期望值为

$$(1 + 2)·0.25 + (2 + 1)·0.375 + (3 + 2)·0.1875 + (3 + 1)·0.1875 = 3.5625。$$