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