{"raw_statement":[{"iden":"statement","content":"_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._\n\nLimak is always either happy or sad. His mood switches with probability $p$ every second. If Limak is happy right now, what is the probability that he's happy after $n$ seconds?\n\nAn integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point.\n\nPrint one line with the answer. The absolute error allowed is $10^(-6)$.\n\nIn the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy.\n\nIn the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all.\n\n"},{"iden":"input","content":"An integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point."},{"iden":"output","content":"Print one line with the answer. The absolute error allowed is $10^(-6)$."},{"iden":"examples","content":"Input1 0.7\nOutput0.3000000000\nInput2 0.1\nOutput0.8200000000\nInput11 0.06\nOutput0.6225404294\n"},{"iden":"note","content":"In the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy.In the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ p \\in (0,1) $ be the probability of mood switch per second.  \nLet $ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $, be the number of seconds.  \nLet $ h_n $ be the probability that Limak is happy after $ n $ seconds, given he starts happy.\n\n**Constraints**  \n$ 0 < p < 1 $, with at most 9 decimal digits.  \n$ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $\n\n**Objective**  \nCompute $ h_n $, where the state transition is governed by:  \n$$\nh_0 = 1, \\quad h_{k} = (1 - p) h_{k-1} + p (1 - h_{k-1}) \\quad \\text{for } k \\geq 1\n$$  \nEquivalently:  \n$$\nh_n = \\frac{1 + (1 - 2p)^n}{2}\n$$","simple_statement":"Limak is happy now. Each second, he switches mood with probability p. What’s the probability he’s still happy after n seconds?","has_page_source":false}