{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Mandarin Chinese](https://www.codechef.com/download/translated/SNCKFL21/mandarin/BAKERY.pdf), [Russian](https://www.codechef.com/download/translated/SNCKFL21/russian/BAKERY.pdf), and [Vietnamese](https://www.codechef.com/download/translated/SNCKFL21/vietnamese/BAKERY.pdf) as well.\n\nYou are the owner of a bakery and you have $m$ employees who serve the customers.\n\nWhen a customer enters the bakery, he waits in line behind other customers who are waiting (or he is the first of the line if there are no other customers waiting).\n\nWhenever there is an employee who is not serving anybody and there is at least one customer waiting in line, one employee immediately starts serving the first person in the line (who, therefore, leaves the line). Serving a customer requires exactly $d$ seconds.\n\nThe waiting time of a customer is the number of seconds elapsed between his entrance in the bakery and the moment someone starts serving him.\n\nYou have just opened the bakery today, and you know that, for each $i\u003d0,1,\\dots,n-1$, with probability $p$ a customer will enter the bakery exactly $i$ seconds after the opening (these $n$ events are independent and the probability $p$ is the same for all of them).\n\nWhat is the expected value of the total waiting time of all the customers (that is, the sum of the waiting times of all the customers)?"}},{"title":"Input Format","value":{"format":"MD","content":"- The only line of the input contains the three integers $n$, $m$, $d$ and the real number $p$ – the number of seconds at which a customer may enter, the number of employees, the amount of seconds necessary to serve a customer, the probability that a customer enters at any given second."}},{"title":"Output Format","value":{"format":"MD","content":"Print a single real number, the expected value of the total waiting time of all the customers. Your answer is considered correct if its relative or absolute error does not exceed $10^{-6}$."}},{"title":"Constraints","value":{"format":"MD","content":"- $1\\le n\\le 50\\,000$ \n- $1\\le m\\le 10$\n- $1\\le d\\le 1000$\n- $0.4\\le p\\le 0.6$\n- The number $p$ is given with exactly $4$ digits after the decimal point."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 5 0.4000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.6400000000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThere is only one employee, it requires $5$ seconds to serve a customer and the probability that a customer enters at a given second is $0.4$.\n\nThe total waiting time is $0$ unless a customer enters at second $0$ (and is immediately served) and another customer enters after one second and has to wait for $5-1\u003d4$ seconds before being served. The probability of this series of events is $0.4^2$; hence the expected total waiting times is $0.4^2\\cdot 4 \u003d 0.64$."}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 1000 0.5000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e124.7500000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nIf there are in total at most $2$ customers, then noone waits since there are two employees. Hence, the total waiting time is $0$ unless there are $3$ customers, which happens with probability $0.5^3$. In such case, the last customer waits for $1000-2\u003d998$ seconds. Hence the answer is $0.5^3\\cdot 998 \u003d 124.75$."}},{"title":"Sample 3","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3 9 0.5891\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.1875381171\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 4","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e40 10 30 0.4567\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e86.7734103628\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}