A Mad Tea Party
– Killing Time! As if he would like that! If you hadn't quarreled with him, you could ask him for anything you want...
Alice's Adventures in Wonderland (translated by N.M. Demurova)
Time won't budge now! The clock is stuck at half-past five... It's always tea time here, and the dishes never get washed!
– Here's the plan, – said the March Hare, – we'll prepare large servings of tea. Each serving consists of N cups arranged in a row. We'll pour green tea into some cups, ensuring no two consecutive cups have green tea, and in the remaining cups, we'll brew classic English black tea.
– I wonder how many different servings we can create? – asked the Dormouse, waking up briefly before dozing off again.
– As many as possible, that's how many we'll make! – the Hatter exclaimed. – Then we'll raise some number M to that power and drink it.
– Wow! What kind of number will that be and what will we toast to? – yawned the Dormouse, waking up once more.
– A number is just a number, simply enormous, beyond counting. – Alice mused aloud. – But it doesn't matter, you can calculate it modulo some number K!
Input
The input file contains three natural numbers M, N, and K. All numbers do not exceed 10^9.
Output
Output a single number – the answer.