Задача Hanoysoft
Герой NetOI Вася Пупкин решил слегка подзаработаь на своем умении решать сложные задачи по информатике. Для того, чтобы устроится в компанию Megasoft, Вася пришел на собеседование, где ему предложили собрать ханойские башни. Вася начал собирать и определил, что тут что-то не так – ни один диск невозможно переложить с первого стержня на третий и наоборот. Вася все же переложил все диски, но доказать Главному Директору фирмы Гиллу Бейтсу, что количество перекладываний минимально, не смог. Помогите Гиллу Бейтсу и Васе найти минимальное количество ходов.
Технические условия. Программа Hanoysoft читает с клавиатуры количество дисков N (1<=N<=10000), далее через пробел номера начального и конечного стержней A B (1<=A, B<=3, A<>B). Программа выводит на экран минимальное количесво перекладываний дисков по модулю 1000000007.
Примеры
Ввод
2 1 2
Вывод
4
Ввод
3 3 1
Вывод
26