Божевільніше чаювання
– Вбити Час! Хіба таке йому може спдобатись! Якби ти з ним не сварилась, могла б просити у нього все, що хочеш...
Пригоди Аліси в країні чудес (переклад Н.М. Демурової)
Час тепер і палець об палець не вдарить! І на годиннику завжди пів на шосту… Туть завжди час пити чай, навіть посуд ніколи вимити!
– Значить так, – сказав Березневий Заєць, – будемо готувати величезні порції чаю. Одна порція – це N чашок, разставлених у ряд. Причому в якісь чашки ми наллємо зелений чай, але так, щоб не було двох підряд чашок з зеленим чаєм, а в інших чашках заваримо класичний англійській чай, чорний звичайно.
– Цікаво, скільки ж таких різних порцій можна зробити? – поцікавилась прокиувшись Соня і знову заснула.
– А скільки можна, стільки і зробимо! – оживився Болванщик. – А потім ще яке-небудь число M піднесено до цієї степені і вип'ємо.
– Ого! І що ж цео за число таке получиться і за що пити будемо? – позіхаючи запитала знову проктнувшись Соня.
– Число як число, просто дуже велике, таке й не порахуєш. – подумала вголос Аліса. – Хоча не важливо, по модулю якого-небудь числа K можна порахувати!
Вхідні дані
У вхідному файлі міститься три натуральних числа M, N і K. Всі числа не перевищують 10^9.
Вихідні дані
У вихідний файл виведіть єдине число – відповідь.