Андрей очень не любит Ханой за его консервативность — уже сотни лет самыми высокими зданиями там считаются три древние башни, между которыми каждый год переносят гигантские кольца по одному и тому же алгоритму (см. замечание). Каждый год Андрея мучает осознание того, что гигантские деньги тратятся на какое-то непонятное развлечение — ещё бы, двигают эти кольца с помощью кучи подъемных кранов, перекрывая центр города на несколько дней! Но прогресс не стоит на месте, и уже в следующем году в Ханое будут построены дополнительно k башен поменьше, на каждой из которых можно будет поместить не более одного кольца одновременно. Когда Андрей прочитал об этом, его тут же заинтересовало, какое минимальное количество действий переноса для n колец потребуется после этого нововведения. Сам он не хочет тратить ни секунды времени на этот ненавистный ему город, поэтому просит вас помочь произвести этот несложный подсчёт.