Giải bài trực tuyến

yenthanh132 vừa mới mua được một chiếc siêu máy tính, mạnh gấp trăm lần siêu máy tính mạnh nhất thế giới hiện nay - Sequoia - có thể tính được 16,32 triệu tỷ (16,32 x 10¹⁵) phép tính trong một giây. Để thử nghiệm sức mạnh chiếc siêu máy tính của mình, yenthanh132 đã viết ra một chương trình đơn giản để tính phép tính các phép tính có dạng a^b mod c. Kết quả chiếc siêu máy tính này đã tính ra kết quả trong chớp nhoáng mặc dù yenthanh132 đã nhập vào những số cực kì lớn.

Nhưng với tính vốn rất cẩu thả của mình, yenthanh132 sợ có sai sót trong chương trình vừa viết nên muốn kiểm tra lại, nhưng nếu tiến hành kiểm tra thì yenthanh132 sẽ lại sợ có sai sót trong quá trình kiểm tra nên sẽ phải tiến hành kiểm tra lại quá trình kiểm tra trước đó của mình... đó sẽ là một vòng lặp vô tận... chỉ mới liên tưởng đến việc đó thôi mà yenthanh132 đã muốn xỉu rồi @@

Bạn là một người tốt bụng, và cũng là một lập trình viên siêu hạng, tuy không có được chiếc siêu máy tính như yenthanh132 nhưng hãy giúp anh ta tính kết quả của bài toán a^b mod c một cách chính xác để yenthanh132 có thể lấy kết quả của bạn để kiểm tra xem chương trình của anh ta xuất ra có đúng không.

Input

- Dòng đầu tiên chứa số a. (2 <= a < 10^1000000)

- Dòng thứ hai chứa số b. (1 <= b < 10^1000000)

- Dòng chứ ba chứa số c. (2<=c<=10⁹)

Chú ý: số a,b có thể có độ dài lên tới 999999 chữ số.

Output

- Một dòng duy nhất là kết quả của phép tính a^b mod c

Ví dụ

Input 1:
2
5
1000000

Output 1:
32

Input 2:
123
456
123456

Output 2:
17505