Cho ~A, B~ và ~\text{MOD}~ là các số nguyên dương. Tính giá trị ~A^B\ \% \text{ MOD}~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~A\ (A ≤ 10^{100000})~;
• Dòng thứ hai gồm số nguyên dương ~B\ (B ≤ 10^{100000})~;
• Dòng thứ ba chứa một số nguyên dương ~\text{MOD}\ (\text{MOD} ≤ 10^9 + 10)~.

Mô tả bộ test:

• ~20\%~ số test có ~\text{MOD} = 10~;
• ~30\%~ số test khác có ~\text{MOD}~ là số nguyên tố;
• ~50\%~ số test còn lại không giới hạn gì thêm.

Output

• In ra giá trị cần tính.

Sample

Input #1

3
2
7

Output #1

2

Problem source: Kc97ble - Free Contest