Задача 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