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