You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述 $1s$ $512mb$

小明是一名质检员，今天要去一个工厂去检查产品质量。

这个工厂提供了$n$个样品，编号为$1,2,...,n$，其中，有一个样品是不合格产品，这个不合格产品会等概率的在这$n$个样品中产生。

小明有一台检测设备，每次检测，小明可以选择一个样品，然后放入检测设备，有以下两种情况：

（1）如果小明放进去的样品刚好就是那个不合格产品，则设备会直接识别出结果，小明的任务就完成了。

（2）如果小明放进去的样品是合格品，则设备有$p$的概率，正确地提示小明不合格产品的编号比这个样品大还是小，有$1-p$的概率，错误地提示小明不合格样品的编号比这个样品大还是小。

举个例子，比如现在一共有$10$个样品，$p=0.7$，不合格样品实际上是在$3$，那么，如果小明把第$5$个样品投入进去，则机器有$0.7$的概率提示小明不合格样品在$[1,4]$中，$0.3$的概率提示小明不合格样品在$[6,10]$中。

又比如，当前不合格样品只剩两种可能，则无论小明用哪一个样品来检测，机器都只能返回正确，或是样品在另一个里，就不存在$1-p$的概率瞎说了。

小明想找到不合格样品的编号，于是他决定，执行下述算法：

假设当前不合格样品所在区间是$[l,r]$，首先用机器检测$\lfloor \frac{l+r}{2} \rfloor$这个编号的样品$k$次（保证$k$是奇数）。

如果这个样品恰好是不合格品，则完成任务。

否则，认可机器回答较多的那一边，然后继续执行上述算法。

举个例子，比如小明询问了样品$5$一共$7$次，机器有$4$次回答了左边，$3$次回答了右边，则小明就认为不合格品在$5$的左边。

现在，我们知道$n,p,k$，请帮助小明算一算，他的这个算法有多少概率能找到不合格品。

输入格式

第一行输入三个数$n,p,k$。其中$p$是$double$类型的实数。

输出格式

输出一个数字表示答案。

输出一个实数表示答案，保留四位小数。

5 1.00 1

1.0000

样例解释 #1

机器不会说谎，小明自然永远不会算错。

3 0.8 1

0.8667

样例解释2

如果不合格品在$2$，则小明第一次就会找到不合格品。

如果不合格品在$1$或者$3$，则小明第一次询问$2$的时候，有$0.8$的概率被引导到正确的位置，$0.2$的概率引导到错误的位置。

总概率是$0.8\times \frac{2}{3} + 1\times \frac{1}{3}=0.866667$

10 0.8 3

0.8412

数据范围

测试点1：$p=1$。

测试点2-4：$n\leq 10,p=0.8$。

测试点5-6：$k=1$。

测试点7-10：$n\leq 1000$。

测试点11-16：$n\leq 10^5$。

测试点1-20：$1\leq n\leq 10^{16},1\leq k\leq 11,0.5\leq p\leq 1$。保证$k$是奇数。