\textit{-- Убить Время! Разве такое ему может понравиться! Если б ты с ним не ссорилась, могла бы просить у него все, что хочешь...} \textit{Приключения Алисы в стране чудес (перевод Н.М. Демуровой)} \includegraphics{https://static.e-olymp.com/content/57/573616c724146a4f73636347c6b6b36544f2d324.jpg} Время теперь и палец о палец не ударит! И на часах всегда полшестого… Здесь всегда пора пить чай, даже посуду некогда вымыть! \textit{--} \textit{Значит так}, \textit{--} сказал Мартовский Заяц, \textit{--} \textit{будем готовить огромные порции чаю. Одна порция -- это }\textbf{N}\textit{ чашек, расставленных в ряд. Причём в какие-то чашки мы нальём зелёный чай, но так, чтобы не было двух подряд чашек с зелёным чаем, а в остальных чашках заварим классический английский чай, чёрный естественно.} \textit{--} \textit{Интересно, сколько же таких различных порций можно сделать?} \textit{--} поинтересовалась проснувшаяся Соня и опять уснула. \textit{-- А сколько можно, столько и сделаем!} \textit{--} оживился Болванщик. \textit{--} \textit{А потом ещё какое-нибудь число }\textbf{M}\textit{ возведём в эту степень и выпьем.} \textit{-- Ого! И что же это за число такое получится и за что пить будем? -- зевая }спросила опять проснувшаяся Соня. \textit{--} \textit{Число как число, просто очень большое, такое и не посчитаешь. -- }подумала вслух Алиса. \textit{--} \textit{Хотя не важно, по модулю какого-нибудь числа }\textbf{K}\textit{ можно посчитать!} \InputFile Во входном файле содержится три натуральных числа \textbf{M}, \textbf{N} и \textbf{K}. Все числа не превосходят \textbf{10^9}. \OutputFile В выходной файл выведите единственное число -- ответ.