Божевільніше чаювання#719
Тепер Час не рухається! Годинник завжди показує пів на шосту... Тут завжди час чаювання, і посуд ніколи не миють!
– Ось план, — сказав Березневий Заєць, ми приготуємо великі порції чаю. Кожна порція складається з чашок, розташованих у ряд. У деякі чашки ми наллємо зелений чай, але ніколи в дві сусідні чашки. В інших буде класичний англійський чорний чай.
– Цікаво, скільки різних порцій ми можемо зробити? — запитав Сонько, прокинувшись на мить перед тим, як знову заснути.
– Скільки завгодно! Стільки й зробимо! — вигукнув Капелюшник. Тоді ми піднесемо якесь число до цього ступеня і вип'ємо його.
– Ого! А що це за число буде та що ж тоді виголосимо за тост? — позіхнув Сонько, знову прокинувшись.
– Число є просто числом, величезним, надто великим, щоб порахувати. Але це не має значення, можна обчислити його за модулем якогось числа ! — міркувала вголос Аліса.
У вхідному файлі записано три натуральних числа , та . Всі числа не перевищують 10^9.
Виведіть єдине число — відповідь.
Приклад 1