Холодными зимними вечерами в Томске очень скучно — оказаться на улице в такую пору не хочется никому. Жители Томска, чтобы коротать время, сидя в теплых квартирах, придумывают себе много различных игр. Одной из таких игр является «Цветная Jenga».
Для этой игры используются деревянные блоки трех цветов: красного, зеленого и синего. Из них составляется башня из n уровней. Каждый из уровней состоит из трех деревянных блоков. Блоки на каждом из уровней могут быть произвольных цветов, но всегда расположены вплотную и параллельно друг другу. Пример такой башни можно увидеть на изображении.
В эту игру играет ровно один человек. Раз в минуту игрок бросает специальную игральную кость, которая имеет шесть граней. Две грани этой кости — зеленые, две — синие, одна — красная и одна — черная. Выпадение каждой из граней равновероятно.
Если выпадает грань красного, зеленого или синего цвета, то игрок в эту минуту обязан достать из башни любой блок такого цвета так, чтобы башня не упала. Если сделать это невозможно, то игрок ждет до конца минуты, не трогая башню. Так же следует ждать до конца минуты, не трогая башню, если выпала черная грань игральной кости. Доставать блоки из самого верхнего уровня башни (независимо от того достроен он или нет) запрещается.
После того, как игрок достал блок, он обязан положить его на верх башни так, чтобы образовать новый уровень или достроить верхний уровень, состоящий из ранее помещенных туда блоков. Вновь построенные уровни должны обладать всеми теми же свойствами, что и начальные уровни. Если верхний уровень не достроен, то новый уровень начинать запрещается.
Чтобы башня не упала, в каждом из уровней, кроме верхнего, должен оставаться хотя бы один блок. При этом если на каком-то из этих уровней остался ровно один блок и он не является средним, то башня падает.
Игра заканчивается в тот момент, когда в башне больше нет ни одного блока, который можно достать так, чтобы башня не упала.
Вот какую замечательную игру могут придумать жители города Томска. Интересно сколько минут может продлиться такая игра, если игрок будет действовать оптимально? Если игрок действует оптимально, то он в любой момент старается выбрать доставаемый блок так, чтобы минимизировать математическое ожидание продолжительности игры.
Ваша задача — написать программу, которая определит математическое ожидание искомого количества минут.