Для натуральних чисел ~a~, ~N~, ~p~ (~1\leqslant a < 2^{63}~, ~1\leqslant N < 2^{63}~, ~1\leqslant p < 2^{63}~) виведiть ~(a^N) \bmod p~, тобто залишок вiд цiлочисельного дiлення ~a^N~ на ~p~.

Вхідні дані

Вхiднi данi слiд прочитати зi стандартного входу (клавiатури). В один рядок через пропуски (пробіли) будуть вводитися багато трійок натуральних чисел ~a~, ~N~, ~p~, всередині кожної з трійок ~a~, ~N~, ~p~ задані в~указаному порядку, та взятi з дiапазонiв, указаних у попередньому абзацi. Кількість трійок ніяк не вказується, слід читати, доки вони не вичерпаються. Гарантовано, що:

• між числами всередині рядка рівно по одному пропуску (пробілу);
• після останнього числа останньої трійки нема пропуску і є переведення рядка;
• зразу після переведення рядка вхідні дані закінчуються.

Результати

Результати (стільки знайдених значень ~(a^N) \bmod p~, скільки у вхідних даних було трійок) слід вивести на стандартний вихід (екран), кожне в окремому рядку.

Примітка 1

Говорячи про дисципліну «Алгоритми і структури даних», повні бали за цю задачу можливі, лише якщо розв'язати цю задачу, не користуючись ні вбудованою довгою арифметикою (отже, й мовою Python, де довга арифметика настільки вбудована, що аж неможливо її відключити), ні бібліотечним готовим методом обчислення такого виразу, навіть якщо Ви зумієте викликати його при перевірці на сайті.

Примітка 2

Так склалося, що тест 1 – тест з умови, тести з 2 по 21 — тести, які були на цій задачі колись, а тести від 22 до 99 сильно спрощені тим, що в них записано рівно по одній трійці, тобто одному прикладу ~a~, ~N~, ~p~. Розв'язок, що вміє обробити багато таких трійок, повинен вміти обробити також і одну.