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