Илья устал от олимпиадного программирования, ушел из университета и устроился на работу в метрополитен. Перед ним поставили задачу определения нагрузки на эскалатор.
Пусть n человек стоят в очереди на эскалатор. В каждую секунду происходит одно из двух: либо первый человек в очереди с вероятностью p заходит на эскалатор, либо первый человек в очереди с вероятностью (1 - p) остается стоять на месте, не в силах совладать с боязнью эскалаторов, задерживая при этом всю очередь за ним.
Формально говоря, i-й в очереди не сможет зайти на эскалатор, пока на него не зайдут люди с номерами от 1 до i - 1 включительно. За одну секунду может зайти только один человек. Так как эскалатор бесконечный, то единожды зайдя на него, человек никогда с него не сойдёт, т. е. будет ехать на нем в эту и любую последующую секунды. Илье нужно посчитать математическое ожидание количества людей, которые будут находиться на эскалаторе после t секунд.
Вам необходимо помочь ему в решении этой непростой задачи.