As you might know, gardening trends are constantly subject to change. Not too long ago, everyone wanted to decorate their garden with an immense, lush ternary tree. Nowadays, it is however more common for homeowners to want only a simple, slender unary tree. Alice and Emmy saw a clear business opportunity here, so they founded the Botanical Alternative Pruning Cooperative. For a fair price, they will turn any ternary tree into a unary tree in no time!
Currently, they are travelling to a customer who has a complete ternary tree of height $$$n$$$: there is a root at the bottom layer, and each vertex has $$$3$$$ neighbouring children in the next layer, continuing until layer $$$n$$$, which consists of $$$3^n$$$ leaves. The leaves come in two varieties: some of the leaves are green, while others are teal. From experience, Alice and Emmy know that every leaf is green with probability $$$0.5 + p$$$ and teal with probability $$$0.5 - p$$$. The colours of different leaves are independent from each other.
To prune the tree, they will start at the root vertex. Alice will cut off one of the three branches extending from this vertex, then Emmy will cut one of the two other branches. Then they both climb up along the remaining branch to the next branching vertex and repeat this process $$$n$$$ times, until they reach a leaf. Each time, Alice gets to cut the first branch, and Emmy cuts the second branch.
However, there is some disagreement on which branches to cut: Alice believes that they should do the cutting in such a way that the remaining leaf is green, while Emmy thinks that the remaining leaf should be teal. Thus, they will both cut branches in such a way to try to get the final remaining leaf to be of their preferred colour.
Assuming Alice and Emmy make optimal cuts, what is the probability that the final leaf will be green? Note that both Alice and Emmy will be able to see all the colours of the leaves before they start cutting the tree.
An example of a tree of height $$$2$$$, like in Sample Input 4. In this instance of a tree, the final leaf is teal. The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n\leq 10^6$$$), the height of the tree.
- One line with a floating point number $$$p$$$ ($$$-0.5 \lt p \lt 0.5$$$, $$$p \neq 0$$$), where the probability of any leaf being green is $$$0.5+p$$$. $$$p$$$ is given in scientific notation, consisting of the following three parts (which are not separated by any whitespace):
- a floating point number $$$m$$$ ($$$1 \leq m \lt 10$$$ or $$$-10 \lt m \leq -1$$$) given with at most $$$10$$$ digits after the decimal point, the mantissa,
- the character 'e', which is shorthand for "$$$\cdot 10^\wedge$$$" (times ten to the power of),
- an integer $$$e$$$ ($$$-10^7 \leq e \leq -1$$$), the exponent.
Output the probability that the final remaining leaf is green.
Your answer should have an absolute error of at most $$$10^{-6}$$$.
1 -4e-1
0.028
10 -2.10e-2
1.5245881e-3
256 1.2345e-46
0.6448034868
2 7.7777777777e-10000000
0.5
